New standard transaction types: time to schedule a blockchain split?

It seems to me the fastest path to very secure, very-hard-to-lose bitcoin wallets is multi-signature transactions.

To organize this discussion: first, does everybody agree?

ByteCoin pointed to a research paper that gives a scheme for splitting a private key between two people, neither of which every knows the full key, but, together, both can DSA-sign transactions. That's very cool, but it involves high-end cutting-edge crypto like zero-knowledge proofs that I know very little about (are implementations available? are they patented? have they been thoroughly vetted/tested? etc). So I'm assuming that is NOT the fastest way to solving the problem.

If anybody has some open-source, patent-free, thoroughly-tested code that already does DSA-key-splitting, speak up please.

I've been trying to get consensus on low-level 'standard' transactions for transactions that must be signed by 2 or 3 keys; current draft proposal is here: https://gist.github.com/39158239e36f6af69d6f and discussion on the forums here: https://bitcointalk.org/index.php?topic=38928.0 ... and there is a pull request that is relevant here: https://github.com/bitcoin/bitcoin/pull/319

I still think it is a good idea to enable a set of new 'standard' multisignature transactions, so they get relayed and included into blocks. I don't want to let "the perfect become the enemy of the good" -- does anybody disagree?

The arguments against are that if the proposed standard transactions are accepted, then the next step is to define a new kind of bitcoin address that lets coins be deposited into a multisignature-protected wallet.

And those new as-yet-undefined bitcoin addresses will have to be 2 or 3 times as big as current bitcoin addresses, and will be incompatible with old clients.

So, if we are going to have new releases that are incompatible with old clients why not do things right in the first place, implement or enable opcodes so the new bitcoin addresses can be small, and schedule a block chain split for N months from now.

My biggest worry is we'll say "Sure, it'll only take a couple days to agree on how to do it right" and six months from now there is still no consensus on exactly which digest function should be used, or whether or not there should be a new opcode for arbitrary boolean expressions involving keypairs. And people's wallets continue to get lost or stolen.

wow, with all the feature requests and bug fixing that needs to be done you want to go off on a tangent.

Vision my friend, once centered on robust architecture, may then be directed on a hard left turn.

Lets get a feature road map done, bug fix and testing framework set up

... or fork this puppy to folks that can execute the above.

-rick

On Wed, Aug 24, 2011 at 8:12 AM, Gavin Andresen <gavinandresen@gmail•com>wrote:

> It seems to me the fastest path to very secure, very-hard-to-lose
> bitcoin wallets is multi-signature transactions.
>
> To organize this discussion: first, does everybody agree?
>
> ByteCoin pointed to a research paper that gives a scheme for splitting
> a private key between two people, neither of which every knows the
> full key, but, together, both can DSA-sign transactions.  That's very
> cool, but it involves high-end cutting-edge crypto like zero-knowledge
> proofs that I know very little about (are implementations available?
> are they patented?  have they been thoroughly vetted/tested?  etc).
> So I'm assuming that is NOT the fastest way to solving the problem.
>
> If anybody has some open-source, patent-free, thoroughly-tested code
> that already does DSA-key-splitting, speak up please.
>
>
> I've been trying to get consensus on low-level 'standard' transactions
> for transactions that must be signed by 2 or 3 keys; current draft
> proposal is here:
>  https://gist.github.com/39158239e36f6af69d6f
> and discussion on the forums here:
>  https://bitcointalk.org/index.php?topic=38928.0
> ... and there is a pull request that is relevant here:
>  https://github.com/bitcoin/bitcoin/pull/319
>
>
> I still think it is a good idea to enable a set of new 'standard'
> multisignature transactions, so they get relayed and included into
> blocks.  I don't want to let "the perfect become the enemy of the
> good" -- does anybody disagree?
>
> The arguments against are that if the proposed standard transactions
> are accepted, then the next step is to define a new kind of bitcoin
> address that lets coins be deposited into a multisignature-protected
> wallet.
>
> And those new as-yet-undefined bitcoin addresses will have to be 2 or
> 3 times as big as current bitcoin addresses, and will be incompatible
> with old clients.
>
> So, if we are going to have new releases that are incompatible with
> old clients why not do things right in the first place, implement or
> enable opcodes so the new bitcoin addresses can be small, and schedule
> a block chain split for N months from now.
>
> My biggest worry is we'll say "Sure, it'll only take a couple days to
> agree on how to do it right" and six months from now there is still no
> consensus on exactly which digest function should be used, or whether
> or not there should be a new opcode for arbitrary boolean expressions
> involving keypairs.  And people's wallets continue to get lost or
> stolen.
>
>
>
> --
> --
> Gavin Andresen
>
>
> ------------------------------------------------------------------------------
> EMC VNX: the world's simplest storage, starting under $10K
> The only unified storage solution that offers unified management
> Up to 160% more powerful than alternatives and 25% more efficient.
> Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

On Wed, Aug 24, 2011 at 11:12 AM, Gavin Andresen <gavinandresen@gmail•com> wrote:

> It seems to me the fastest path to very secure, very-hard-to-lose
> bitcoin wallets is multi-signature transactions.
>
> To organize this discussion: first, does everybody agree?

It's a good tool which we should have in our tool-belt.

Though it's a bit of when you are a hammer all problems are nails. This issue can also be addressed by things like external private key protectors. But someone would have to build one.

Someone might be more inclined to build such a thing if the software had good support for tracking public keys without private keys, and generating unsigned transactions for export to the device for signing.

> ByteCoin pointed to a research paper that gives a scheme for splitting
> a private key between two people, neither of which every knows the

[snip]

> So I'm assuming that is NOT the fastest way to solving the problem.

Regardless, it might be useful to contact the authors.

> I still think it is a good idea to enable a set of new 'standard'
> multisignature transactions, so they get relayed and included into
> blocks.  I don't want to let "the perfect become the enemy of the
> good" -- does anybody disagree?

I agree.

> The arguments against are that if the proposed standard transactions
> are accepted, then the next step is to define a new kind of bitcoin
> address that lets coins be deposited into a multisignature-protected
> wallet.
>
> And those new as-yet-undefined bitcoin addresses will have to be 2 or
> 3 times as big as current bitcoin addresses, and will be incompatible
> with old clients.
>
> So, if we are going to have new releases that are incompatible with
> old clients why not do things right in the first place, implement or
> enable opcodes so the new bitcoin addresses can be small, and schedule
> a block chain split for N months from now.

One way of doing this would be to have an address which hashes an ordered concatenation of many addresses (perhaps plus a length argument). To redeem you provide the public keys which are signing, plus the addresses which aren't signing, and the receiver validates.

If it can be done, then yes, I agree it would be worth forking the chain.

This _feels_ like something which could and should be done with the existing (but disabled opcodes).

It's not exclusive, however, with a long N-address address type for multisig destinations. We could support that _now_ and defer the 'compressed version' until after people have experience with this usage. The only cost would be supporting this address type forever, which isn't that bad.

It's also important to note that incompatibility wouldn't be complete: The only limit is that old clients couldn't send funds to escrow addresses— which is an issue no matter how you encode the information.

On Wed, Aug 24, 2011 at 8:45 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:

> On Wed, Aug 24, 2011 at 11:12 AM, Gavin Andresen
> <gavinandresen@gmail•com> wrote:
> > It seems to me the fastest path to very secure, very-hard-to-lose
> > bitcoin wallets is multi-signature transactions.
> >
> > To organize this discussion: first, does everybody agree?
>
> It's a good tool which we should have in our tool-belt.
>
> Though it's a bit of when you are a hammer all problems are nails.
> This issue can also be addressed by things like external private key
> protectors.  But someone would have to build one.
>
> Someone might be more inclined to build such a thing if the software
> had good support for tracking public keys without private keys, and
> generating unsigned transactions for export to the device for signing.
>
> > ByteCoin pointed to a research paper that gives a scheme for splitting
> > a private key between two people, neither of which every knows the
> [snip]
> > So I'm assuming that is NOT the fastest way to solving the problem.
>
> Regardless, it might be useful to contact the authors.
>
> > I still think it is a good idea to enable a set of new 'standard'
> > multisignature transactions, so they get relayed and included into
> > blocks.  I don't want to let "the perfect become the enemy of the
> > good" -- does anybody disagree?
>
> I agree.
>
> > The arguments against are that if the proposed standard transactions
> > are accepted, then the next step is to define a new kind of bitcoin
> > address that lets coins be deposited into a multisignature-protected
> > wallet.
> >
> > And those new as-yet-undefined bitcoin addresses will have to be 2 or
> > 3 times as big as current bitcoin addresses, and will be incompatible
> > with old clients.
> >
> > So, if we are going to have new releases that are incompatible with
> > old clients why not do things right in the first place, implement or
> > enable opcodes so the new bitcoin addresses can be small, and schedule
> > a block chain split for N months from now.
>
> One way of doing this would be to have an address which hashes an
> ordered concatenation of many addresses (perhaps plus a length
> argument). To redeem you provide the public keys which are signing,
> plus the addresses which aren't signing, and the receiver validates.
>
> If it can be done, then yes, I agree it would be worth forking the chain.
>
> This _feels_ like something which could and should be done with the
> existing (but disabled opcodes).
>
>
> It's not exclusive, however, with a long N-address address type for
> multisig destinations.  We could support that _now_ and defer the
> 'compressed version' until after people have experience with this
> usage.  The only cost would be supporting this address type forever,
> which isn't that bad.
>
> It's also important to note that incompatibility wouldn't be complete:
> The only limit is that old clients couldn't send funds to escrow
> addresses— which is an issue no matter how you encode the information.
>
>
> ------------------------------------------------------------------------------
> EMC VNX: the world's simplest storage, starting under $10K
> The only unified storage solution that offers unified management
> Up to 160% more powerful than alternatives and 25% more efficient.
> Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

On Aug 24, 2011 10:12 AM, "Gavin Andresen" <gavinandresen@gmail•com> wrote:

>
> If anybody has some open-source, patent-free, thoroughly-tested code
> that already does DSA-key-splitting, speak up please.
>

If the caveat of a trusted third party is acceptable and, as greg mentioned, if there was a way to export unsigned transactions and then import/broadcast after signing this becomes fairly trivial.

Shamir's + 3rd party to combine and sign means no protocol level changes.

Process could work something like this:

Parties agree to endpoint destination address and provide it to third party. Third party generates key and provides shares to each party in the txn and the resulting address to both as well. Third party destroys (preferably, never stores) private key. Sender sends to address. Both parties after confirmation of reciept of goods or what have you provide shares back to third party who uses the privkey to xfer inputs to the previously agreed upon destination subtracting their fee.

This resembles more traditional escrow setups and relies on the trust of a third party, which is not ideal, but would be fairly simple to implement until the other proposals could be better investigated and implemented.

On Wednesday, August 24, 2011 11:12:10 AM Gavin Andresen wrote:

> So, if we are going to have new releases that are incompatible with
> old clients why not do things right in the first place, implement or
> enable opcodes so the new bitcoin addresses can be small, and schedule
> a block chain split for N months from now.

If a block chain split is to occur, it makes sense to try to fix as many
problems as possible:
- Replace hard limits (like 1 MB maximum block size) with something that can
  dynamically adapt with the times. Maybe based on difficulty so it can't be
  gamed?
- Adjust difficulty every block, without limits, based on a N-block sliding
  window. I think this would solve the issue when the hashrate drops
  overnight, but maybe also add a block time limit, or perhaps include the
  "current block" in the difficulty calculation?
- 21 million really isn't enough if Bitcoin ever takes off, even with
  100,000,000 units per BTC. Replacing the "Satoshi" 64-bit integers with
  "Satoshi" variable-size fractions (ie, infinite numerator + denominator)
  would create infinite possibilities of future divison, allowing people to
  not only do nBTC and pBTC, but also exact 1/3 of any quantity. Transaction
  size would go up based on the number of primes involved in an amount, which
  would encourage discarding annoying primes in transaction fees.
- Standardize everything on network (big) endian.

I'm sure others can think of other chain-splitting fixes that wouldn't be too much work to fix.

On Wed, Aug 24, 2011 at 11:12:10AM -0400, Gavin Andresen wrote:

> So, if we are going to have new releases that are incompatible with
> old clients why not do things right in the first place, implement or
> enable opcodes so the new bitcoin addresses can be small, and schedule
> a block chain split for N months from now.

What was the reason for disabling these opcodes in the first place? I can understand wanting to prevent excessive signature-verification, or limitation of arithmetic to a limited amount of bits, but completely disabling all arithmetic beyond addition and subtraction, and all bitwise operations seems very limiting to me. Thus, if we agree to do a future incompatible update, i would vote to re-enable these, and maybe allow arithmetic up to 520 or 1024 bits numbers.

While we're at it, some additional opcodes could be useful. Either a custom operator to do boolean evaluation, or a few more lowlevel operations. Given the presence of bitwise operators, you could have scripts that process a sequence of pubkey/signature pairs, build up a number in which each bit corresponds to a valid signature, and then do some bitwise checks on this number. I'd argue that a "count number of bits set in number" opcode would be very useful for this.

In short: I'm in favor of re-enabling opcodes, and possibly adding an OP_BITCOUNT operation.

On Wednesday, August 24, 2011 12:18:54 PM Pieter Wuille wrote:

> While we're at it, some additional opcodes could be useful.

Also:
- Access to the block height it's part of. While this can be abused,
  transactions accessing it can be given a big red flag in the GUI or
  something. Legitimate uses include "Clearcoin" functionality in the script
  itself.
- Remove the 100 confirmation requirement for spending generated coins. If
  they are respent before 100 confirmations, clients can/should flag the new
  outputs as also "generated" or "recently generated" so recipients are aware
  of the risk. It would be especially handy for pool operators if blocks could
  contain a transaction spending one of the same block's generation in
  addition to other non-generated coins, and specifying the full amount as a
  fee to safely add coins to the generation. Right now, if I were to embed a
  25 BTC fee-only transaction, there is a risk that Deepbit could grab that
  transaction for their own, and fork. By making pool payouts all generated,
  there is no risk to paying invalid blocks instantly (since if the block is
  invalid, so is the payout made in it).

On Wed, Aug 24, 2011 at 12:15 PM, Luke-Jr <luke@dashjr•org> wrote:

> - Replace hard limits (like 1 MB maximum block size) with something that can
> dynamically adapt with the times. Maybe based on difficulty so it can't be
> gamed?

Too early for that.

> - Adjust difficulty every block, without limits, based on a N-block sliding
>  window. I think this would solve the issue when the hashrate drops
>  overnight, but maybe also add a block time limit, or perhaps include the
>  "current block" in the difficulty calculation?

The quantized scheme limits the amount of difficulty skew miners can create by lying about timestamps to about a half a percent. A rolling window with the same time constant would allow much more skew.

> Replacing the "Satoshi" 64-bit integers with
> "Satoshi" variable-size fractions (ie, infinite numerator + denominator)

Increasing precision I would agree with but, sadly, causing people to need more than 64 bit would create a lot of bugs.

infinite numerator + denominator is absolutely completely and totally batshit insane. For one, it has weird consequences that the same value can have redundant encodings.

Most importantly, it suffers factor inflation: If you spend inputs 1/977 1/983 1/991 1/997 the smallest denominator you can use for the output 948892238557.

Not to mention that the idiots writing financial software can only barely manage to not use radix-2 floating point on everything. Asking them to use arbitrary rational numbers with mixed radix will never fly.

> - Remove the 100 confirmation requirement for spending generated coins. If
>  they are respent before 100 confirmations, clients can/should flag the new
>  outputs as also "generated" or "recently generated" so recipients are aware
> of the risk.

Please lets not make bitcoin _less_ trustworthy.

The 100 block maturity on generated coins is good. The generation from an orphaning is lost forever like the losing side of a double spend, but far far worse... because orphaning happens all the time on its own without any malice.

I agree it's obnoxious that you can't pad your generation payouts without creating more transactions, but I don't see a solution for that. Repeat the addresses... make up for it by increasing your payout threshold.

On Wed, 24 Aug 2011 11:12 -0400, "Gavin Andresen" <gavinandresen@gmail•com> wrote:

> To organize this discussion: first, does everybody agree?

Yes. The feature will be very good.

> I still think it is a good idea to enable a set of new 'standard'
> multisignature transactions, so they get relayed and included into
> blocks.  I don't want to let "the perfect become the enemy of the
> good" -- does anybody disagree?

Please do enable any transactions that seem to be a possible solution. Even if this client doesn't ever implement any of them, alternative clients can try them.

> My biggest worry is we'll say "Sure, it'll only take a couple days to
> agree on how to do it right" and six months from now there is still
> no consensus on exactly which digest function should be used, or
> whether or not there should be a new opcode for arbitrary boolean
> expressions involving keypairs.  And people's wallets continue to get
> lost or stolen.

I agree that something should be done with what we have now. It *will* take months to properly figure out how to add chain-forking features for this. If we want to consider all of the unrelated feature proposals, it might take years of discussion...

However, as I said in the forum thread, I think it would be better for people using this protection to receive at a normal address and then create new transactions at their end. Then no one has to handle huge addresses, and the sender will never have to pay abnormal fees or deal with incompatibilities. There will be a short period of time when the recipient's money is unprotected, but I think this is worth it. A better scheme can be made later after chain-forking features are figured out.

On Wednesday, August 24, 2011 12:46:42 PM Gregory Maxwell wrote:

> On Wed, Aug 24, 2011 at 12:15 PM, Luke-Jr <luke@dashjr•org> wrote:
> > - Replace hard limits (like 1 MB maximum block size) with something that
> > can dynamically adapt with the times. Maybe based on difficulty so it
> > can't be gamed?
>
> Too early for that.

Dynamically adapting would be by design never too early/late. Changing from a fixed 1 MB will fork the block chain, which should be a minimized event.

> > - Adjust difficulty every block, without limits, based on a N-block
> > sliding window. I think this would solve the issue when the hashrate
> > drops overnight, but maybe also add a block time limit, or perhaps
> > include the "current block" in the difficulty calculation?
>
> The quantized scheme limits the amount of difficulty skew miners can
> create by lying about timestamps to about a half a percent. A rolling
> window with the same time constant would allow much more skew.

Depends on the implementation, I'd think.

> > Replacing the "Satoshi" 64-bit integers with
> > "Satoshi" variable-size fractions (ie, infinite numerator + denominator)
>
> Increasing precision I would agree with but, sadly, causing people to
> need more than 64 bit would create a lot of bugs.
>
> infinite numerator + denominator is absolutely completely and totally
> batshit insane. For one, it has weird consequences that the same value
> can have redundant encodings.

So? You can already have redundant transactions simply by changing the order of inputs/outputs. A good client would minimize the transaction size by reducing them, of course.

> Most importantly, it suffers factor inflation: If you spend inputs
> 1/977 1/983 1/991 1/997 the smallest denominator you can use for the
> output 948892238557.

I already tried to address this in my original mail. If I had those 4 coins, I would use a denominator of 987 and discard the difference as fees.

On Wed, Aug 24, 2011 at 9:46 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:

> On Wed, Aug 24, 2011 at 12:15 PM, Luke-Jr <luke@dashjr•org> wrote:
>
> > - Replace hard limits (like 1 MB maximum block size) with something that
> can
> > dynamically adapt with the times. Maybe based on difficulty so it can't
> be
> > gamed?
>
> Too early for that.
>
>

Could you provide a reference to why in your estimation it is "to early." Simpy stating this as fact isn't enough to sway demand.

> - Adjust difficulty every block, without limits, based on a N-block
> sliding
> >  window. I think this would solve the issue when the hashrate drops
> >  overnight, but maybe also add a block time limit, or perhaps include the
> >  "current block" in the difficulty calculation?
>
> The quantized scheme limits the amount of difficulty skew miners can
> create by lying about timestamps to about a half a percent. A rolling
> window with the same time constant would allow much more skew.
>
> > Replacing the "Satoshi" 64-bit integers with
> > "Satoshi" variable-size fractions (ie, infinite numerator + denominator)
>
> Increasing precision I would agree with but, sadly, causing people to
> need more than 64 bit would create a lot of bugs.
>
>

how about we agree that increasing precision is a goal and worry about how to encode that once its on the road map.

> infinite numerator + denominator is absolutely completely and totally
> batshit insane. For one, it has weird consequences that the same value
> can have redundant encodings.
>
> Most importantly, it suffers factor inflation: If you spend inputs
> 1/977 1/983 1/991 1/997 the smallest denominator you can use for the
> output 948892238557.
>
> Not to mention that the idiots writing financial software can only
> barely manage to not use radix-2 floating point on everything. Asking
> them to use arbitrary rational numbers with mixed radix will never
> fly.
>
> > - Remove the 100 confirmation requirement for spending generated coins.
> If
> >  they are respent before 100 confirmations, clients can/should flag the
> new
> >  outputs as also "generated" or "recently generated" so recipients are
> aware
> > of the risk.
>
> Please lets not make bitcoin _less_ trustworthy.
>
> The 100 block maturity on generated coins is good. The generation from
> an orphaning is lost forever like the losing side of a double spend,
> but far far worse... because orphaning happens all the time on its own
> without any malice.
>
> I agree it's obnoxious that you can't pad your generation payouts
> without creating more transactions, but I don't see a solution for
> that. Repeat the addresses... make up for it by increasing your payout
> threshold.
>
>
> ------------------------------------------------------------------------------
> EMC VNX: the world's simplest storage, starting under $10K
> The only unified storage solution that offers unified management
> Up to 160% more powerful than alternatives and 25% more efficient.
> Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

On Wed, Aug 24, 2011 at 1:07 PM, Rick Wesson <rick@support-intelligence•com> wrote:

> On Wed, Aug 24, 2011 at 9:46 AM, Gregory Maxwell <gmaxwell@gmail•com> wrote:
>> On Wed, Aug 24, 2011 at 12:15 PM, Luke-Jr <luke@dashjr•org> wrote:
>>
>> > - Replace hard limits (like 1 MB maximum block size) with something that
>> > can
>> > dynamically adapt with the times. Maybe based on difficulty so it can't
>> > be
>> > gamed?
>> Too early for that.
> Could you provide a reference to why in your estimation it is "to early."
>  Simpy stating this as fact isn't enough to sway demand.

Can you provide a reference to this 'demand' a post by Luke isn't enough to support the claim of demand.

We're not at maximum size right now (thankfully).

We don't know what the network dynamics would look like at that traffic level. So how could we competently say what the right metrics would be to get the right behavior there? Thats what I meant by too early.

On Wed, Aug 24, 2011 at 10:19 AM, Gregory Maxwell <gmaxwell@gmail•com>wrote:

> On Wed, Aug 24, 2011 at 1:07 PM, Rick Wesson
> <rick@support-intelligence•com> wrote:
> > On Wed, Aug 24, 2011 at 9:46 AM, Gregory Maxwell <gmaxwell@gmail•com>
> wrote:
> >> On Wed, Aug 24, 2011 at 12:15 PM, Luke-Jr <luke@dashjr•org> wrote:
> >>
> >> > - Replace hard limits (like 1 MB maximum block size) with something
> that
> >> > can
> >> > dynamically adapt with the times. Maybe based on difficulty so it
> can't
> >> > be
> >> > gamed?
> >> Too early for that.
> > Could you provide a reference to why in your estimation it is "to early."
> >  Simpy stating this as fact isn't enough to sway demand.
>
> Can you provide a reference to this 'demand' a post by Luke isn't
> enough to support the claim of demand.
>
> how about trend, its a hard limit and as you acknowledged below we are not

there yet; however the trend is for more transactions and we will bump into the limit. Being good architects we should consider how to scale or explicitly state why its a good idea not to.

-rick

> We're not at maximum size right now (thankfully).
>
> We don't know what the network dynamics would look like at that
> traffic level. So how could we competently say what the right metrics
> would be to get the right behavior there?  Thats what I meant by too
> early.
>

no one ever "knows" what the network dynamics are going to be in developing infrastructure -- so lets not kid our selves, in being able to estimate this before the code is even written.

-rick

"Gavin Andresen" <gavinandresen@gmail•com> wrote:

> It seems to me the fastest path to very secure, very-hard-to-lose
> bitcoin wallets is multi-signature transactions.
>
> To organize this discussion: first, does everybody agree?

I agree. For example, a corporate wallet can require threshold signatures to disburse. Or for personal use you can have a couple of additional keys, one stored on a secure device for confirmation and one offline as emergency backup if you lose your secure device.

...

> I've been trying to get consensus on low-level 'standard' transactions
> for transactions that must be signed by 2 or 3 keys; current draft
> proposal is here:
>  https://gist.github.com/39158239e36f6af69d6f
> and discussion on the forums here:
>  https://bitcointalk.org/index.php?topic=38928.0
> ... and there is a pull request that is relevant here:
>  https://github.com/bitcoin/bitcoin/pull/319

For context - I am the author of the latter.

> I still think it is a good idea to enable a set of new 'standard'
> multisignature transactions, so they get relayed and included into
> blocks.  I don't want to let "the perfect become the enemy of the
> good" -- does anybody disagree?
>
> The arguments against are that if the proposed standard transactions
> are accepted, then the next step is to define a new kind of bitcoin
> address that lets coins be deposited into a multisignature-protected
> wallet.
>
> And those new as-yet-undefined bitcoin addresses will have to be 2 or
> 3 times as big as current bitcoin addresses, and will be incompatible
> with old clients.

Incompatible at the UI level, but not at the block chain level. Changing the block chain rules will be quite an undertaking. You will have to set a block number for the rule change a few months in advance and will have to get agreement from the pools. I think it is important to increase trust in the bitcoin ecosystem sooner than that. The current flat exchange rate and difficulty may be a signal that people are getting risk averse.

> So, if we are going to have new releases that are incompatible with
> old clients why not do things right in the first place, implement or
> enable opcodes so the new bitcoin addresses can be small, and schedule
> a block chain split for N months from now.
>
> My biggest worry is we'll say "Sure, it'll only take a couple days to
> agree on how to do it right" and six months from now there is still no
> consensus on exactly which digest function should be used, or whether
> or not there should be a new opcode for arbitrary boolean expressions
> involving keypairs.  And people's wallets continue to get lost or
> stolen.

That is my worry too. We already have working code for this (pull 319), and the addresses are not so long as to be unusable. I hope we can move forward on the existing code and in parallel move forward on block chain rule proposals at an agreed upon block number.

This discussion is convincing me that scheduling a blockchain split is definitely the wrong idea at this time. We can revisit in N months, when we've got a roadmap and nice unit tests and a bunch of well-tested patches for fixing all of the things that aught to be fixed when we DO decide a blockchain split is necessary.

There seems to be rough consensus that new, imperfect standard transactions are a good-enough short term solution.

On Wed, Aug 24, 2011 at 1:57 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:

> This discussion is convincing me that scheduling a blockchain split is
> definitely the wrong idea at this time.  We can revisit in N months,

Strongly agreed...

Sorry for keeping this short but I'm in holiday and reading/writing on my phone is a pain.

On Aug 24, 2011 4:12 PM, "Gavin Andresen" <gavinandresen@gmail•com> wrote:

>
> It seems to me the fastest path to very secure, very-hard-to-lose
> bitcoin wallets is multi-signature transactions.
>
> To organize this discussion: first, does everybody agree?

It's a great way for companies to secure their assets.

>
> ByteCoin pointed to a research paper that gives a scheme for splitting
> a private key between two people, neither of which every knows the
> full key, but, together, both can DSA-sign transactions.  That's very
> cool, but it involves high-end cutting-edge crypto like zero-knowledge
> proofs that I know very little about (are implementations available?
> are they patented?  have they been thoroughly vetted/tested?  etc).
> So I'm assuming that is NOT the fastest way to solving the problem.
>
> If anybody has some open-source, patent-free, thoroughly-tested code
> that already does DSA-key-splitting, speak up please.

Since. we have the possibility o add other signature schemes to the protocol we could add an rsa-like scheme which allows m-out-of-n signatures. It works by distributing shares of the key which are points on a curve having the actual key as 0-value. It does not require special length for the key so if ecdsa allows something similar there need not be anything changed.

>
> I've been trying to get consensus on low-level 'standard' transactions
> for transactions that must be signed by 2 or 3 keys; current draft
> proposal is here:
>  https://gist.github.com/39158239e36f6af69d6f
> and discussion on the forums here:
>  https://bitcointalk.org/index.php?topic=38928.0
> ... and there is a pull request that is relevant here:
>  https://github.com/bitcoin/bitcoin/pull/319
>
>
> I still think it is a good idea to enable a set of new 'standard'
> multisignature transactions, so they get relayed and included into
> blocks.  I don't want to let "the perfect become the enemy of the
> good" -- does anybody disagree?

Would be a first step.

>
> The arguments against are that if the proposed standard transactions
> are accepted, then the next step is to define a new kind of bitcoin
> address that lets coins be deposited into a multisignature-protected
> wallet.
>
> And those new as-yet-undefined bitcoin addresses will have to be 2 or
> 3 times as big as current bitcoin addresses, and will be incompatible
> with old clients.
>
> So, if we are going to have new releases that are incompatible with
> old clients why not do things right in the first place, implement or
> enable opcodes so the new bitcoin addresses can be small, and schedule
> a block chain split for N months from now.
>
> My biggest worry is we'll say "Sure, it'll only take a couple days to
> agree on how to do it right" and six months from now there is still no
> consensus on exactly which digest function should be used, or whether
> or not there should be a new opcode for arbitrary boolean expressions
> involving keypairs.  And people's wallets continue to get lost or
> stolen.
>
>

Just wanted to point you in that alternative direction as it would possibly keep backward compatibility and allow multisignature.

Regards, Chris

>
> --
> --
> Gavin Andresen
>
>

------------------------------------------------------------------------------

> EMC VNX: the world's simplest storage, starting under $10K
> The only unified storage solution that offers unified management
> Up to 160% more powerful than alternatives and 25% more efficient.
> Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

On Wed, Aug 24, 2011 at 3:05 PM, Christian Decker <decker.christian@gmail•com> wrote:

> we could add an rsa-like scheme which allows m-out-of-n signatures. It works
> by distributing shares of the key which are points on a curve having the
> actual key as 0-value. It does not require special length for the key so if
> ecdsa allows something similar there need not be anything changed.

This works fine for ECC. But it requires that the composite key signer has simultaneous access to all the key-parts, so it doesn't solve the "my PC has malware" problem.

On Aug 24, 2011 3:29 PM, "Gregory Maxwell" <gmaxwell@gmail•com> wrote:

>
> On Wed, Aug 24, 2011 at 3:05 PM, Christian Decker
> <decker.christian@gmail•com> wrote:
> > we could add an rsa-like scheme which allows m-out-of-n signatures. It

works

> > by distributing shares of the key which are points on a curve having the
> > actual key as 0-value. It does not require special length for the key so

if

> > ecdsa allows something similar there need not be anything changed.
>
> This works fine for ECC.  But it requires that the composite key
> signer has simultaneous access to all the key-parts, so it doesn't
> solve the "my PC has malware" problem.

I don't think anything simple enough to actually be used by people in general does. Same concept as what I proposed earlier before nanotube gave me the context for Gavin's intent on irc.

Now that I'm understanding the use case I really think the best way to go about this initially is like you said earlier.

Provide methods to export/import unsigned txns, provide methods to run the GUI in a way that can track your own addresses with only pubkeys available to the client, provide methods to sign and import/export/broadcast signed txns.

With these tools offline wallets become feasible. Combined with wallet crypto I think this is really the best that can be done to protect users from themselves in a way that isn't too complicated for them to actually use.

Hi Gavin (the list escaped the cc...),

I participated also in the hacakathon Sunday @ OnlyOneTV and I felt that this had a strong chance to diverge. So - yes - I agree - no "constitution" changes now. Further, I have thought later on on the analogy of a clerk and a safe.

WHen you enter the bank you hand over your money to the clerk (one key) - then after the clerks wallet has been filled over the day _he_ transfers the money to the safe (3 keys). My point is do we really need the customer to bypass the clerk and have 3 key addresses, or could we just leave it to the/a client to implement the multisign transaction after the money has been received - as a transfer to a safe? This would greatly simplify the problem and cover the vast majority of use cases. Not covered in this is huge single transfers where the intruder of a single key system finds it profitable to reveal their intrusion by grabbing the entire wallet.

Put in another way - do we *really* need to couple the securing of the wallet to creating a new address type ?

Cheers,

M

On 24/08/2011, at 19:57, Gavin Andresen wrote:

> This discussion is convincing me that scheduling a blockchain split is
> definitely the wrong idea at this time.  We can revisit in N months,
> when we've got a roadmap and nice unit tests and a bunch of
> well-tested patches for fixing all of the things that aught to be
> fixed when we DO decide a blockchain split is necessary.
>
> There seems to be rough consensus that new, imperfect standard
> transactions are a good-enough short term solution.
>
> --
> --
> Gavin Andresen
>
> ------------------------------------------------------------------------------
> EMC VNX: the world's simplest storage, starting under $10K
> The only unified storage solution that offers unified management
> Up to 160% more powerful than alternatives and 25% more efficient.
> Guaranteed. http://p.sf.net/sfu/emc-vnx-dev2dev
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists•sourceforge•net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Michael Gronager, PhD Owner Ceptacle / NDGF Director, NORDUnet A/S Jens Juels Gade 33 2100 Copenhagen E Mobile: +45 31 62 14 01 E-mail: gronager@ceptacle•com

On Thu, Aug 25, 2011 at 3:39 AM, Michael Grønager <gronager@ceptacle•com> wrote:

> Put in another way - do we *really* need to couple the securing of the wallet to creating a new address type ?

Nope.

I should have been more clear in my initial email and in the proposal-- I am not proposing anything more than just agreeing on the very lowest-level infrastructure, so there is a solid foundation upon which we can build a couple of key very-high-priority features.

I wanted to talk about it now so there is rough consensus on what to
put on the road map, and to get as many smart brains looking at the
proposal and making it as good as possible.  Current proposal is at:
  https://gist.github.com/39158239e36f6af69d6f

I have two issues with it:

1) groffer reports that there's a bug in CHECKMULTISIG (pops too many arguments off the stack), so perhaps we should avoid using it at all. Fixing the bug would change its behavior, and is not an option because that would cause a blockchain split. We absolutely need unit tests and better documentation for how CHECKMULTISIG behaves (perhaps it is working as intended, and Satoshi just messed up the description of what it does in the comment).

2) How often will the 1-of-3 and 3-of-3 cases be used? I included them just for completeness, but perhaps they should be dropped for now so there is less code to write and test. I just don't imagine there are many cases where you have exactly three parties and 1-of-3 or 3-of-3 are required to spend.

On Thu, Aug 25, 2011 at 3:39 AM, Michael Grønager <gronager@ceptacle•com> wrote: the customer to bypass the clerk and have 3 key addresses, or could we just leave it to the/a client to implement the multisign transaction after the money has been received - as a transfer to a safe? This would greatly simplify the problem and cover the vast majority of use cases. Not covered in this is huge single transfers where the intruder of a single key system finds it profitable to reveal their intrusion by grabbing the entire wallet.

Obviously these things don't need to be hard coupled, since they're useful independently. But I don't agree with the premise that being able to pay directly into an escrow using an address isn't essential at least as an eventual feature.

The bank analogy falls down because in our threat model people are replacing the bank teller with a convincing facsimile (malware turning your computer against you). Funds can be stolen in a microsecond, so any exposure isn't good.

Again, I'm not arguing to delay anything— just pointing out that the ability to have usable addresses (they can be long) that encode a couple escrow destination.

Perhaps just an address type that can encode any payment script? User provides the inputs, sets the outputs plus and additional outputs, and signs. Client refuses to pay to an address if the resulting transaction fails IsStandard.

On Thu, Aug 25, 2011 at 1:18 PM, Gavin Andresen <gavinandresen@gmail•com> wrote:

> 2) How often will the 1-of-3 and 3-of-3 cases be used? I included them
> just for completeness, but perhaps they should be dropped for now so
> there is less code to write and test.  I just don't imagine there are
> many cases where you have exactly three parties and 1-of-3 or 3-of-3
> are required to spend.

3-of-3 in particular seems somewhat important to me (group trust accounts). I'd really rather not drop use cases unless we're not confident that they can't be tested sufficiently simply because it'll just mean another cycle of testing later someday to test them and, honestly, a more uphill argument as the usecases get narrower and narrower.

I'll spend some cycles testing whatever cases make it in.

On Thu, Aug 25, 2011 at 02:31:49PM -0400, Gregory Maxwell wrote:

> Perhaps just an address type that can encode any payment script?  User
> provides the inputs, sets the outputs plus and additional outputs, and
> signs. Client refuses to pay to an address if the resulting
> transaction fails IsStandard.

On the github pull request I posted a general scheme that can convert arbitrary expressions over signature-checks (given in RPL notation) to bitcoin scripts. Maybe we can define an address type that encodes an expression in RPL form (which should be more compact and more easily parseable)?

That basically just means the usual bitcoin scripts, with two extra pseudo- instructions: one that represents an address check, one that represents an pubkey check.

For example (same example as on the pull req), the expression a1 OR (a2 AND a3) OR COUNT(a4,a5,a6)>1 (with a1-a6 given addresses) can be given in RPL form as

  ADDR<a1> ADDR<a2> ADDR<a3> BOOLAND BOOLOR ADDR<a4> ADDR<a5>
  ADD ADDR<a6> ADD 1 GREATERTHAN BOOLOR

Which is 13 bytes + 6*20 bytes, instead of the 54 bytes + 6*20 bytes for the real bitcoin output script.

On Thu, Aug 25, 2011 at 4:10 PM, Pieter Wuille <pieter.wuille@cs•kuleuven•be> wrote:

> Which is 13 bytes + 6*20 bytes, instead of the 54 bytes + 6*20 bytes for the
> real bitcoin output script.

So 187 bytes in base-58? I think pretty darn good for a destination with 6 keys and complicated rules. I like that a lot.

On Thu, Aug 25, 2011 at 04:29:03PM -0400, Gregory Maxwell wrote:

> On Thu, Aug 25, 2011 at 4:10 PM, Pieter Wuille
> <pieter.wuille@cs•kuleuven•be> wrote:
> > Which is 13 bytes + 6*20 bytes, instead of the 54 bytes + 6*20 bytes for the
> > real bitcoin output script.
>
> So 187 bytes in base-58? I think pretty darn good for a destination
> with 6 keys and complicated rules. I like that a lot.

Some extra estimates: * single address: 21 bytes (36 characters), 27 bytes script * 1-out-of-2: 43 bytes (66 characters), 56 bytes script * 2-out-of-3: 67 bytes (98 characters), 88 bytes script * (a and b) or c: 65 bytes (96 characters), 85 bytes script

If I remember the details correctly you could combine (lagrange interpolation) the results of m smaller encryptions/signatures without ever sharing the secret key share itself. No idea if that is possible with ecdsa at all, but it sure would solve quite a few problems, as it would allow several independent servers to share a secret key, sign transactions with it, but no m-1 compromised machines would endanger the whole balance. I will definitely look into it when I'm back from holidays.

Cheers, Cdecker On Aug 24, 2011 9:29 PM, "Gregory Maxwell" <gmaxwell@gmail•com> wrote:

> On Wed, Aug 24, 2011 at 3:05 PM, Christian Decker
> <decker.christian@gmail•com> wrote:
>> we could add an rsa-like scheme which allows m-out-of-n signatures. It

works

>> by distributing shares of the key which are points on a curve having the
>> actual key as 0-value. It does not require special length for the key so

if

>> ecdsa allows something similar there need not be anything changed.
>
> This works fine for ECC. But it requires that the composite key
> signer has simultaneous access to all the key-parts, so it doesn't
> solve the "my PC has malware" problem.

> 1) groffer reports that there's a bug in CHECKMULTISIG (pops too many
> arguments off the stack), so perhaps we should avoid using it at all.

What is the bug, exactly? Perhaps it can be worked around.

> On the github pull request I posted a general scheme that can convert arbitrary
> expressions over signature-checks (given in RPL notation) to bitcoin scripts.
> Maybe we can define an address type that encodes an expression in RPL form (which
> should be more compact and more easily parseable)?

What are the use cases for this?

From a mobile apps perspective, it doesn't make much sense to have arbitrary scripts in a user-facing address. The software has to be able to present some kind of reasonable user interface given an address, it has to explain what is going to happen to the users money and so on. From this perspective, doing pattern matching against some encoded script template is annoying and inefficient. It'd be better to just define another type of URI for each kind of transaction you wish to support. This is doubly true because often to do the more interesting contracts, you need out of band protocols, so the "address" would probably specify some information that's not in the final output script, like a rendezvous point.

> It seems to me the fastest path to very secure, very-hard-to-lose
> bitcoin wallets is multi-signature transactions.

Agreed.

That said I'm not sure it makes sense for payers to care about the details of how somebody is protecting their wallets (which is what new address types means). It's possible for a users software to notice inbound payments to a regular Bitcoin address and then immediately respend them to multi-signed outputs. This way key management can be simpler as you don't need to integrate it with your shopping cart software or anything like that - you can just do the usual thing of pre-generating a few hundred thousand addresses, fill up your cart implementation and go. When a payment is received, your wallet software can keep an eye on how much unlocked balance it has and start locking value once it goes over a pre-set amount, or use any other policy the user might have.

This fits with my belief that we'll eventually move away from senders attaching tx fees, instead receivers will respend the fee-less transaction adding whatever fee they believe is appropriate (eg, maybe it's very low in the case of a buyer with good reputation, or higher for unknown buyers). It doesn't make a whole lot of sense for buyers to have to attach more fees just because the merchant is using complex wallet policies.

Whitelisting the basic CHECKMULTISIG form (assuming it can be made to work) seems uncontroversial, why not do it today? The forms designed to make fancier addresses be embeddable inside QRcodes, can come later if people feel it's necessary. I'm still not convinced it is.

Once malware can't just email wallets to the attacker, or steal the keys when the user decrypts due to a second factor, the next easiest attack is to that malware can rewrite addresses on-screen as it sees fit, forwarding small payments so the user doesn't notice then stealing a big one. To solve that, Bitcoin addresses need to contain not only a pubkey[hash] but some kind of endpoint the second factor can use to verify ownership of the key. It can be discussed later, I don't think there are many possible designs here so it shouldn't be too controversial.

> Whitelisting the basic CHECKMULTISIG form (assuming it can be made to
> work) seems uncontroversial, why not do it today?

That seems like the right way forward.

I just wrote a unit test and stepped through the CHECKMULTISIG code to
see exactly what the bug is, and the offending line is:
   797	                    int isig = ++i;
   798	                    i += nSigsCount;

It should be just int isig = i;

The result is CHECKMULTISIG expects one extra item on the stack, so the workaround would be a standard transaction type of the form:

scriptSig: OP_0 sig1...m scriptPubKey: m pubkey1...n n OP_CHECKMULTISIG

On Fri, Aug 26, 2011 at 01:09:37PM +0200, Mike Hearn wrote:

> > On the github pull request I posted a general scheme that can convert arbitrary
> > expressions over signature-checks (given in RPL notation) to bitcoin scripts.
> > Maybe we can define an address type that encodes an expression in RPL form (which
> > should be more compact and more easily parseable)?
>
> What are the use cases for this?
>
> From a mobile apps perspective, it doesn't make much sense to have
> arbitrary scripts in a user-facing address. The software has to be
> able to present some kind of reasonable user interface given an
> address, it has to explain what is going to happen to the users money
> and so on. From this perspective, doing pattern matching against some
> encoded script template is annoying and inefficient. It'd be better to
> just define another type of URI for each kind of transaction you wish
> to support. This is doubly true because often to do the more
> interesting contracts, you need out of band protocols, so the
> "address" would probably specify some information that's not in the
> final output script, like a rendezvous point.

You're quite right - currently addresses encode a particular output script, and the client pattern matches to know how to deal with the incoming funds. It's far from sure this will remain the case in the future. Maybe we'll have an out of band protocol over which a request "i want to pay you for item X" is sent, with the required transaction output as answer.

A generic way for encoding complex transaction scripts in a compact form may be useful for "manual" playing with them - but I agree that we should probably wait for a use case for this.

Independent from the question of complex-script-addresses are useful, I do think it is useful (and possible, see pull req) to allow a class of scripts that represent boolean expressions over signature checks to pass the IsStandard() test - that way we make sure that whenever in the future we want to support creating such an expression, there will at least be a to encode it in a way that the network will accept it. The only question is what possible problems there are with accepting them.

>> Whitelisting the basic CHECKMULTISIG form (assuming it can be made to
>> work) seems uncontroversial, why not do it today?
>
> That seems like the right way forward.
>
> I just wrote a unit test and stepped through the CHECKMULTISIG code to
> see exactly what the bug is, and the offending line is:
>    797	                    int isig = ++i;
>    798	                    i += nSigsCount;
>
> It should be just   int isig = i;
>
> The result is CHECKMULTISIG expects one extra item on the stack, so
> the workaround would be a standard transaction type of the form:
>
> scriptSig: OP_0 sig1...m
> scriptPubKey: m pubkey1...n  n OP_CHECKMULTISIG

Right, that is the workaround in pull 319.

There is another disadvantage to CHECKMULTISIG - you currently can only have 1000 of these in a block. This is because a CHECKMULTISIG is counted as 20 sigop operations in GetSigOpCount, and you can have a maximum of 20000 sigops in a block (MAX_BLOCK_SIGOPS). This is in CheckBlock so won't change anytime soon.

If you want to use HASH160 based addresses, CHECKMULTISIG looks even less attractive. The shortest script with CHECKSIG is something like:

0 OVER 2SWAP CHECKSIG SWAP HASH160 {} EQUAL BOOLAND ADD // n times m GREATERTHANOREQUAL

( thanks to coblee https://gist.github.com/39158239e36f6af69d6f#gistcomment-47017 )

I think this is actually as short as the shortest you can do with CHECKMULTISIG.

Another issue that came up during pull 319 discussion is whether to support more general cases or more specific cases. For example, should we optimize for the 1-of-2, 2-of-2 and 2-of-3 cases or should we just have one script template for all m-of-n? I would propose focusing on a more general case for the following reasons:

* It is easier to validate one general algorithm than an expanding set of special-purpose functions. For example, I think the most people on this list can validate the coblee script above for all n and m, but faced with a bunch of special purpose scripts they might miss a bug.

* We don't have to expose the most general cases to the API, but it would be nice if we didn't have to keep changing IsStandard as people find use cases for 2-of-4, etc. With IsStandard remaining narrow, innovation with new scripts is stifled because most client won't mine or relay non-standard transactions.

* It would be less work for third-party software to track this (blockexplorer, android wallet).

"Gavin Andresen" <gavinandresen@gmail•com> wrote:

> I wanted to talk about it now so there is rough consensus on what to
> put on the road map, and to get as many smart brains looking at the
> proposal and making it as good as possible.  Current proposal is at:
>   https://gist.github.com/39158239e36f6af69d6f
>
> I have two issues with it:
>
> 1) groffer reports that there's a bug in CHECKMULTISIG (pops too many
> arguments off the stack), so perhaps we should avoid using it at all.
> Fixing the bug would change its behavior, and is not an option because
> that would cause a blockchain split. We absolutely need unit tests and
> better documentation for how CHECKMULTISIG behaves (perhaps it is
> working as intended, and Satoshi just messed up the description of
> what it does in the comment).
>
> 2) How often will the 1-of-3 and 3-of-3 cases be used? I included them
> just for completeness, but perhaps they should be dropped for now so
> there is less code to write and test.  I just don't imagine there are
> many cases where you have exactly three parties and 1-of-3 or 3-of-3
> are required to spend.

Here are some additional use cases:

* Long term lock funds, requiring signatures from 2 officers of a company to disburse (2 of n for n between 3 and 20)

* Short term lock funds, with 2-factor auth to disburse and an additional 2 of n backup in case one of the factors is lost (2-of-2 OR 2-of-n)

* "Escrow" with the the two parties having to agree or one of two backup observers helping in case of disagreement (2-of-2 OR 2-of-3 OR 2-of-3)

* An options contract where the outcome is triggered by a key being broadcast: (Ks AND K1) OR (Kr AND K2) - s gets control of funds if K1 is broadcast, r gets control if K2 is broadcast.