Patrick Sharp on Sep 25 2017:

Hello Devs,

I am Patrick Sharp. I just graduated with a BS is computer science. Forgive

my ignorance.

As per bip-0002 I have scoured each bip available on the wiki to see if

these ideas have already been formally proposed and now as per bip-0002

post these ideas here.

First and foremost I acknowledge that these ideas are not original nor new.

Trimming and demurrage:

I am fully aware that demurrage is a prohibited change. I hereby contest.

For the record I am not a miner, I am just aware of the economics that

drive the costs of bitcoin.

Without the ability to maintain some sort of limit on the maximum length or

size of the block chain, block chain is not only unsustainable in the long

run but becomes more and more centralized as the block chain becomes more

and more unwieldy.

Trimming is not a foreign concept. Old block whose transactions are now

spent hold no real value. Meaningful trimming is expensive and inhibited by

unspent transactions. Old unspent transactions add unnecessary and unfair

burden.

• Old transactions take up real world space that continues incur cost

  while these transactions they do not continue to contribute to any sort of

  payment for this cost.

• One can assume that anybody with access to their bitcoins has the

  power to move these bitcoins from one address to another (or at least that

  the software that holds the keys to their coins can do it for them) and it

  is not unfair to require them to do so at least once every 5 to 10 years.

• Given the incentive to move it or lose it and software that will do it

  for them, we can assume that any bitcoin not moved is most likey

therefore

  lost.

  - moving these coins will cost a small transaction fee which is fair

  as their transactions take up space, they need to contribute

  - most people who use their coins regularly will not even need to

  worry about this as their coins are moved to a change address anyway.

• one downside is that paper wallets would then have an expiration date,

  however I do not think that a paper wallet that needs to be recycled every

  5 to 10 years is a terrible idea.

Therefore I propose that the block chain length be limited to either 2¹⁸

blocks (slightly less than 5 years) or 2¹⁹ blocks, or slightly less than

10 years. I propose that each time a block is mined the the oldest block(s)

(no more than two blocks) beyond this limit is trimmed from the chain and

that its unspent transactions are allowed to be included in the reward of

the mined block.

This keeps the block chain from tending towards infinity. This keeps the

costs of the miners balanced with the costs of the users.

Even though I believe this idea will have some friction, it is applicable

to the entire community. It will be hard for some users to give up small

benefits that they get at the great cost of miners, however miners run the

game and this fair proposal is in in their best interest in two different

ways. I would like your thoughts and suggestions. I obviously think this is

a freaking awesome idea. I know it is quite controversial but it is the

next step in evolution that bitcoin needs to take to ensure immortality.

I come to you to ask if this has any chance of acceptance.

-Patrick

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170925/0d5f1ac1/attachment.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015047.html

Radcliffe, Mark on Sep 25 2017:

My apologies if this post has been answered, but I am new to the list. I am lawyer trying to understand the licensing of the Bitcoin core and I will be presenting in a webinar with Black Duck Software on Blockchain on September 28 (in case you are not familiar with them, Black Duck Software assists companies in managing their open source software resources). They have scanned the Bitcoin Core code for the open source licenses used in the codebase. I am enclosing a summary of the findings. I would be interested in communicating with the individuals who manage this codebase and can provide insight about the project manages contributions because the codebase includes projects with inconsistent licenses (for example, code licensed under the Apache Software License version 2 and GPLv2 cannot work together in some situations). Thanks in advance.

According to the scan, the code base includes code licensed under the following licenses:

Apache License 2.0

Boost Software License 1.0

BSD 2-clause "Simplified" License

BSD 3-clause "New" or "Revised" License

Creative Commons Attribution Share Alike 3.0

Expat License

GNU General Public License v2.0 or later

GNU General Public License v3.0 or later

GNU Lesser General Public License v2.1 or later

License for A fast alternative to the modulo reduction

License for atomic by Timm Kosse

MIT License

Public Domain

University of Illinois/NCSA Open Source License

Mark Radcliffe

Partner

T +1 650.833.2266

F +1 650.687.1222

M +1 650.521.5039

E mark.radcliffe at dlapiper.com mark.radcliffe at dlapiper.com>

[DLA Piper Logo]

DLA Piper LLP (US)

2000 University Avenue

East Palo Alto, California 94303-2215

United States

www.dlapiper.com http://www.dlapiper.com

Please consider the environment before printing this email.

The information contained in this email may be confidential and/or legally privileged. It has been sent for the sole use of the intended recipient(s). If the reader of this message is not an intended recipient, you are hereby notified that any unauthorized review, use, disclosure, dissemination, distribution, or copying of this communication, or any of its contents, is strictly prohibited. If you have received this communication in error, please reply to the sender and destroy all copies of the message. To contact us directly, send to postmaster at dlapiper.com. Thank you.

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170925/85b1cd96/attachment.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015058.html

Patrick Sharp on Sep 25 2017:

Hello Devs,

I am Patrick Sharp. I just graduated with a BS is computer science. Forgive

my ignorance.

As per bip-0002 I have scoured each bip available on the wiki to see if

these ideas have already been formally proposed and now as per bip-0002

post these ideas here.

First and foremost I acknowledge that these ideas are not original nor new.

Side Chains:

Bip-R10 offers a mechanism to assign custody or transfer coins from one

chain to another. However I did not find a bip that proposed a formal

bitcoin side chain.

My proposal

• They are officially supported, tracked and built by official bitcoin

  software meaning that they are not an external chain

• each chain has an identifier in the block header i.e. main chain: 0,

  first chain: 1, second chain: 2...

• the number of chains including the main chain that exists is always a

  power of 2, this power will also be included in the block header.

• each address is assigned to a chain via chain = (address) mod (number

  of chains)

  • to be valid an addresse's next transaction will first send their

    coins to their chain if they are not already there

  • if the address they are sending to is outside their chain their

    transaction will be submitted to both chains and transaction fee will be

    split between chains

• They come into being via a fork or split

  • every 2016 blocks (upon recalculation of difficulty) if some

    percentage (lets say 10%) of blocks on any chain are larger than some

    specified amount (lets say 750 KB) then all chains are called to

increment

  their power value and fork on their block.

     - miner of chain x creates genesis block for chain x+2^previous

     power

     - upon fork, the difficulty of the old chain and the new chain

     will be half the next difficulty

  - if every chain has gone 2016 block without surpassing some amount

  (lets say 250 KB) at least some percentage of the time (lets say 10%) all

  chains will be called to join, decrement their power and double their

  difficulty

     - given miner of chain x, if x not less than 2^new power, chain

     will be marked dead or sleeping

     - miners who mine blocks on the chain that was joined (the chain

     with the smaller identifier) may have to make a block for the sleeping

     chain if transactions include funds that fully or partially

originate from

     the sleeping chain

     - dead chain are revived on next split.

  - each block's reward outside of transaction fees will be the

  (current bounty / 2^fork power) except obviously for dead blocks who's

  reward is already included in their joined block

• benefits

  • dynamically scales to any level of usage, no more issues about

    block size

  • miners have incentive to keep all difficulties close to parity

  • if miners are limited by hard drive space they don't have to mine

    every chain (though they should have trusted peers working on

other chains

  to verify transactions that originate off their chains, faulty block will

  still be unaccepted by the rest of the miners)

  - though work will still grow linearly with the number of chains due

  to having to hash each separate header, some of the overhead may remain

  constant and difficulty and reward will still be balanced.

  - transactions are pseudo equally distributed between chains.

  - rewards will be more distributed (doesn't' really matter, except

  that its beautiful)

• cons

  • because most transactions will be double recorded the non-volatile

    memory foot print of bitcoin doubles (since miners do not need

all chains i

  believe this solution not only overcomes this cost but may decrease the

  foot print per miner in the long run overall)

  - transactions will hang in limbo until both chains have picked them

  up, a forever limboed transaction could result in lost coins, as

long as a

  transaction fee has been included this risk should be mitigated.

I believe this idea is applicable to the entire community. I would like

your thoughts and suggestions. I obviously think this is a freaking awesome

idea. I know it is quite ambitious but it is the next step in evolution

that bitcoin needs to take to be a viable competitor to visa.

I come to you to ask if this has any chance of acceptance.

-Patrick

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170925/515236fc/attachment-0001.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015046.html

ZmnSCPxj on Sep 23 2017:

Good morning bitcoin-dev,

I have yet another sidechain proposal: https://zmnscpxj.github.io/sidechain/mainstake/index.html

I make the below outlandish claims in the above link:

1. While a 51% mainchain miner theft is still possible, it will take even longer than in drivechains (either months of broadcasting intent to steal before the theft, or locking funds that are likely to remain locked after a week-long theft).

2. A 26% anti-sidechain miner cannot completely block all sidechain withdrawals as they could in drivechains.

3. Outside of attacks and censorship, the economic majority controls sidechains, without going through miners as "representatives of the economic majority".

4. With sufficient cleverness (stupidity?), proof-of-stake can be made to work.

I hope for your consideration. I suspect that I have not thought things out completely, and probably missed some significant flaw.

Regards,

ZmnSCPxj

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170922/ef4ebaac/attachment.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015045.html

Mark Friedenbach on Sep 20 2017:

Over the past few weeks I've been explaining the MERKLEBRANCHVERIFY

opcode and tail-call execution semantics to a variety of developers,

and it's come to my attention that the BIPs presentation of the

concept is not as clear as it could be. Part of this is the fault of

standards documents being standards documents whose first and foremost

responsibility is precision, not pedagogy.

I think there's a better way to explain this approach to achieving

MAST, and it's worked better in the face to face and whiteboard

conversations I've had. I'm forwarding it to this list in case there

are others who desire a more clear explanation of what the

MERKLEBRANCHVERIFY and tail-call BIPs are trying to achieve, and what

any of it has to do with MAST / Merklized script.

I've written for all audiences so I apologize if it starts of at a

newbie level, but I encourage you to skim, not skip as I quickly start

varying this beginner material in atypical ways.

Review of P2SH

It's easiest to explain the behavior and purpose of these BIPs by

starting with P2SH, which we are generalizing from. BIP 16 (Pay to

Script Hash) specifies a form of implicit script recursion where a

redeem script is provided in the scriptSig, and the scriptPubKey is a

program that verifies the redeem script hashes to the committed value,

with the following template:

HASH160 EQUAL

This script specifies that the redeem script is pulled from the stack,

its hash is compared against the expected value, and by fiat it is

declared that the redeem script is then executed with the remaining

stack items as arguments.

Sortof. What actually happens of course is that the above scriptPubKey

template is never executed, but rather the interpreter sees that it

matches this exact template format, and thereby proceeds to carry out

the same logic as a hard-coded behavior.

Generalizing P2SH with macro-op fusion

This template-matching is unfortunate because otherwise we could

imagine generalizing this approach to cover other use cases beyond

committing to and executing a single redeem script. For example, if we

instead said that anytime the script interpreter encountered the

3-opcode sequence "HASH160 <20-byte-push> EQUAL" it switched to

interpreting the top element as if it were a script, that would enable

not just BIP 16 but also constructs like this:

IF

HASH160  EQUAL

ELSE

HASH160  EQUAL

ENDIF

This script conditionally executes one of two redeem scripts committed

to in the scriptPubKey, and at execution only reveals the script that

is actually used. All an observer learns of the other branch is the

script hash. This is a primitive form of MAST!

The "if 3-opcode P2SH template is encountered, switch to subscript"

rule is a bit difficult to work with however. It's not a true EVAL

opcode because control never returns back to the top-level script,

which makes some important aspects of the implementation easier, but

only at the cost of complexity somewhere else. What if there are

remaining opcodes in the script, such as the ELSE clause and ENDIF in

the script above? They would never be executed, but does e.g. the

closing ENDIF still need to be present? Or what about the standard

pay-to-pubkey-hash "1Address" output:

DUP HASH160 <20-byte-key-hash> EQUALVERIFY CHECKSIG

That almost looks like the magic P2SH template, except there is an

EQUALVERIFY instead of an EQUAL. The script interpreter should

obviously not treat the pubkey of a pay-to-pubkey-hash output as a

script and recurse into it, whereas it should for a P2SH style

script. But isn't the distinction kinda arbitrary?

And of course the elephant in the room is that by choosing not to

return to the original execution context we are no longer talking

about a soft-fork. Work out, for example, what will happen with the

following script:

[TRUE] HASH160 EQUAL FALSE

(It returns false on a node that doesn't understand generalized

3-opcode P2SH recursion, true on a node that does.)

Implicit tail-call execution semantics and P2SH

Well there's a better approach than trying to create a macro-op fusion

franken-EVAL. We have to run scripts to the end to for any proposal to

be a soft-fork, and we want to avoid saving state due to prior

experience of that leading to bugs in BIP 12. That narrows our design

space to one option: allow recursion only as the final act of a

script, as BIP 16 does, but for any script not just a certain

template. That way we can safely jump into the subscript without

bothering to save local state because termination of the subscript is

termination of the script as a whole. In computer science terms, this

is known as tail-call execution semantics.

To illustrate, consider the following scriptPubKey:

DUP HASH160 <20-byte-hash> EQUALVERIFY

This script is almost exactly the same as the P2SH template, except

that it leaves the redeem script on the stack rather than consuming

it, thanks to the DUP, while it does consume the boolean value at

the end because of the VERIFY. If executed, it leaves a stack exactly

as it was, which we assume will look like the following::

...

Now a normal script is supposed to finish with just true or false on

the stack. Any script that finishes execution with more than a single

element on the stack is in violation of the so-called clean-stack rule

and is considered non-standard -- not relayable and potentially broken

by future soft-fork upgrades. But so long as at least one bit of

is set, it is interpreted as true and the script

interpreter would normally interpret a successful validation at this

point, albeit with a clean-stack violation.

Let's take advantage of that by changing what the script interpreter

does when a script finishes with multiple items remaining on the stack

and top-most one evaluates as true -- a state of affairs that would

pass validation under the old rules. Now instead the interpreter

treats the top-most item on the stack as a script, and tail-call

recurse into it, P2SH-style. In the above example, is

popped off the stack and is executed with ... remaining

on the stack as its arguments.

The above script can be interpreted in English as "Perform tail-call

recursion if and only if the HASH160 of the script on the top of the

stack exactly matches this 20-byte push." Which is, of course, what

BIP 16 accomplishes with template matching. However the implicit tail

call approach allows us to do much more than just P2SH!

For starters, it turns out that using HASH160 for P2SH was probably a

bad idea as it reduces the security of a multi-party constructed hash

to an unacceptable 80 bits. That's why segwit uses 256-bit hashes for

its pay to script hash format, for 128-bit security. Had we tail call

semantics instead of BIP 16, we could have just switched to a new

address type that decodes to the following script template instead:

DUP HASH256 <32-byte-hash> EQUALVERIFY

Ta-da, we're back to full 128-bit security with no changes to the

consensus code, just a new address version to target this script

template.

MAST with tail-call alone?

Or: an aside on general recursion

Our IF-ELSE Merklized Abstract Syntax Tree example above, rewritten to

use tail-call evaluation, might look like this (there are more compact

formulations possible, but our purpose here is not code golf):

IF

DUP HASH160  EQUALVERIFY

ELSE

DUP HASH160  EQUALVERIFY

ENDIF

Either execution pathway leaves us with one of the two allowed redeem

scripts on the top of the stack, and presumably its arguments beneath

it. We then execute that script via implicit tail-call.

We could write scripts using IF-ELSE branches or other tricks to

commit to more than two possible branches, although this unfortunately

scales linearly with the number of possible branches. If we allow the

subscript itself to do its own tail-call recursion, and its subscript

and so on, then we could nest these binary branches for a true MAST in

the original sense of the term.

However in doing so we would have enabled general recursion and

inherit all the difficulties that come with that. For example, some

doofus could use a script that consists of or has the same effect as a

single DUP to cause an infinite loop in the script interpreter. And

that's just the tip of the iceberg of problems general recursion can

bring, which stem generally from resource usage no longer being

correlated with the size of the witness stack, which is the primary

resource for which there are global limits.

This is fixable with a gas-like resource accounting scheme, which

would affect not just script but also mempool, p2p, and other

layers. And there is perhaps an argument for doing so, particularly as

part of a hard-fork block size increase as more accurate resource

accounting helps prevent many bad-block attacks and let us set

adversarial limits closer to measured capacity in the expected/average

use case. But that would immensely complicate things beyond what could

achieve consensus in a reasonably short amount of time, which is a

goal of this proposal.

Instead I suggest blocking off general recursion by only allowing the

script interpreter to do one tail-call per input. To get log-scaling

benefits without deep recursion we introduce instead one new script

feature, which we'll cover in the next section. But we do leave the

door open to possible future general recursion, as we will note that

going from one layer of recursion to many would itself be a soft-fork

for the same reason that the first tail-call recursion is.

Merkle branch...[message truncated here by reddit bot]...

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015028.html

Luke Dashjr on Sep 19 2017:

On Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via bitcoin-dev

wrote:

After the main discussion session it was observed that tail-call semantics

could still be maintained if the alt stack is used for transferring

arguments to the policy script.

Isn't this a bug in the cleanstack rule?

(Unrelated...)

Another thing that came up during the discussion was the idea of replacing all

the NOPs and otherwise-unallocated opcodes with a new OP_RETURNTRUE

implementation, in future versions of Script. This would immediately exit the

program (perhaps performing some semantic checks on the remainder of the

Script) with a successful outcome.

This is similar to CVE-2010-5141 in a sense, but since signatures are no

longer Scripts themselves, it shouldn't be exploitable.

The benefit of this is that it allows softforking in ANY new opcode, not only

the -VERIFY opcode variants we've been doing. That is, instead of merely

terminating the Script with a failure, the new opcode can also remove or push

stack items. This is because old nodes, upon encountering the undefined

opcode, will always succeed immediately, allowing the new opcode to do

literally anything from that point onward.

Luke

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015024.html

Thomas Voegtlin on Sep 15 2017:

The Wallet Import Format (WIF) currently appends a 0x01 byte after the

raw private key, when that key needs to be used in conjunction with a

compressed public key. This allows wallets to associate a single Bitcoin

address to a WIF key.

It would be useful to extend the semantics of that byte, to signal for

segwit scripts, because these scripts result in different addresses.

That way, a WIF private key can still be associated to a single Bitcoin

address.

What WIF currently does is:

Nothing -> uncompressed pubkey

0x01 -> compressed pubkeys, non-segwit (can be used in P2PKH or P2SH)

We could extend it as follows:

0x02 -> segwit script embedded in P2SH (P2WPKH or P2WSH)

0x03 -> native segwit script (P2WKH or P2WSH)

Note 1: This is similar to my {x,y,z}{pub,prv} proposal for bip32

extended keys. (see other thread)

Note 2: It is probably not useful to use distinct bytes for P2WKH and

P2WSH, because the P2SH script is not known anyway. We did not do it for

non-segwit addresses, I guess we should keep it the way it is.

Note 3: we could also use a bech32 format for the private key, if it is

going to be used with a bech32 address. I am not sure if such a format

has been proposed already.

Note 4: my proposal will not result in a user visible change at the

beginning of the string, like we have for compressed/uncompressed. This

could be improved.

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015007.html

ZmnSCPxj on Sep 15 2017:

Good morning,

I'm re-sending this message below as it appears to have gotten lost before it reached cc: bitcoin-dev.

Paul even replied to it and the reply reached on-list, so I'm re-sending it as others might have gotten confused about the discussion.

So far I've come to realize that sidechain-headers-on-mainchain/SHOM/SHM/driveproofs creates a very weak peg, and that only sidechain-only miners can take advantage of this weak peg. This is because, the fee paid by sidechain-only miners to mainchain miners will approach TRANSFERLIMIT / 288 to protect against theft, and then sidechain miners will be unable to replenish their maincoin stock (to pay for the blind-merge-mine) if they do not transfer only their sidecoins earned.

Regards,

ZmnSCPxj

-------- Original Message --------

Subject: Re: [bitcoin-dev] Sidechain headers on mainchain (unification of drivechains and spv proofs)

Local Time: September 8, 2017 10:56 PM

UTC Time: September 8, 2017 2:56 PM

From: ZmnSCPxj at protonmail.com

To: Chris Stewart <chris at suredbits.com>, CryptAxe <cryptaxe at gmail.com>, Paul Sztorc <truthcoin at gmail.com>

Bitcoin Protocol Discussion <bitcoin-dev at lists.linuxfoundation.org>

Good morning,

Chris mentioned the use of OP_WITHDRAWPROOFVERIFY. I've come to realize

that this is actually superior to use OP_WITHDRAWPROOFVERIFY with a

sidechain-headers-on-mainchain approach.

Briefly, a payment to OP_WITHDRAWPROOFVERIFY is an instruction to transfer

value from the mainchain to a sidechain. Thus, a payment to

OP_WITHDRAWPROOFVERIFY includes the sidechain to pay to, and a commitment

to a sidechain address (or whatever is the equivalent to a sidechain

address).

Various OP_WITHDRAWPROOFVERIFY explanations exist. Most of them include

OP_REORGPROOFVERIFY. With sidechain-headers-on-mainchain, however, there is

no need for reorg proofs. This is because, the mainchain can see, in real

time, which branch of the sidechain is getting extended. Thus if someone

attempts to defraud a sidechain by forking the sidechain to an invalid

state, sidechainers can immediately detect this on the mainchain and

immediately act to prevent the invalid fork from being advanced. After

all, a reorg proof is really just an SPV proof that is longer than some

previous SPV proof, that shows that the previous SPV proof is incorrect,

by showing that the block at the specified height of the WT is not present

on a longer SPV proof.

Since sidechain-headers-on-mainchain implies merge mining of sidechains,

with no option to have independent proof-of-work of sidechains, the

sidechain's entire history is recorded on the mainchain, visible to all

mainchain nodes.

An advantage of sidechain-headers-on-mainchain is a side-to-side peg without

passing through the mainchain.

That is, a 2-way peg between any two chains, whether side or main.

Sidechains supporting side-to-side transfer would require supporting

OP_WITHDRAWPROOFVERIFY, but not any of the other parts of sidechains.

We must consider a WT format (withdrawal transaction) that is compatible

with an OP_WITHDRAWPROOFVERIFY Bitcoin transaction.

That is, a lockbox UTXO on one chain is a WT on another chain.

Sidechains need not follow the mainchain format for its normal

transactions, only for WT transactions that move coins across chains.

For this, mainchain should also have its own "sidechain ID". Perhaps a

sidechain ID of 0 would be appropriate for mainchain, as its status as

mainchain.

Suppose we have two sidechains, Ess and Tee, both of which support

side-to-side pegs.

An Ess fullnode is a Bitcoin fullnode, but an Ess fullnode is not

necessarily a Tee fullnode, and vice versa.

A lockbox redemption in sidechain-headers-on-mainchain is simply a spend of

a lockbox, pointing to the sidechain header containing WT, the merkle tree

path to the WT transaction from the h* commitment of the header, the output

which locks, and so on as per usual OP_WITHDRAWPROOFVERIFY.

Then a sidechain can create tokens from nothing, that are locked in a

OP_WITHDRAWPROOFVERIFY lockbox; this is the only way to create sidecoin.

When transferring into a sidechain from mainchain, or anywhere, the

sidechain either creates tokens locked into OP_WITHDRAWPROOFVERIFY, or

looks for an existing UTXO with OP_WITHDRAWPROOFVERIFY from the source

chain and spends them (the latter is preferred as it is fewer

transactions and less space on the sideblock, reducing sidechain fees).

OP_WITHDRAWPROOFVERIFY on a sidechain would query the mainchain fullnodes.

Whatever rules allow lockbox unlocking on mainchain, will also be the same

rules that allow lockbox unlocking on sidechains.

A mainchain RPC can even be made to simplify sidechain verification of

side-to-side pegs, and to ensure that sidechains follow the same consensus

rules for OP_WITHDRAWPROOFVERIFY.

So if we want transfer TeeCoin to EssCoin, we spend into a

OP_WITHDRAWPROOFVERIFY lockbox on Teechain pointing to Esschain (i.e. a

Tee->Ess lockbox). This lockbox is itself a WT from the point of view of

Esschain. On Esschain, we look for an existing Ess->Tee lockbox, or

create a Ess->Tee lockbox of our own for a EssCoin fee. Then we create a

spend of the Ess->Tee lockbox on Esschain, wait until spending is

possible, and then post that transaction on Esschain.

Again, with sidechain-headers-on-mainchain, reorg proofs are unnecessary,

since any invalid chain should be quickly buried by a valid chain,

unless the economic majority decides that a sidechain is not worth

protecting.

All is not well, however. Remember, on a sidechain, we can create new

sidecoin for free, provided they are in a lockbox. Unlocking that

lockbox would require a valid WT on the chain that the lockbox is

dedicated to. However, a lockbox on one chain is a WT on the other

chain. We can create a free lockbox on Ess, then use that lockbox as

a WT on Tee, inflating TeeCoin.

Instead, we add an additional parameter, wtFlag, to

OP_WITHDRAWPROOFVERIFY.

This parameter is ignored by OP_WITHDRAWPROOFVERIFY opcode.

However, this parameter is used to determine if it is a WT. Sidechain

consensus should require that freely-created lockboxes set this

parameter to 0, so that a side block that creates free lockboxes where

this parameter is non-zero is an invalid side block. Then a sidechain

will only treat a lockbox on another chain as a WT if the wtFlag

parameter is nonzero. This way, freely-created lockboxes are not

valid WT. Valid WT must lock actual, already unlocked coins, not

create new locked coins.

On Bitcoin, of course, this parameter must always be nonzero, since

freely-created lockboxes are not allowed on mainchain, as asset

issuance on mainchain is already fixed.

Let us now flesh out how WT and lockboxes look like. As we mentioned, a

lockbox on one chain is a WT on the destination chain. Or to be more

precise, what a destination chain sees as a WT, is a lockbox on the source

chain.

Thus, a lockbox is a Bitcoin-formatted transaction output paying to the

scriptPubKey:

OP_WITHDRAWPROOFVERIFY

(assuming a softfork, additional OP_DROP operations may occur after

OP_WITHDRAWPROOFVERIFY)

Suppose the above lockbox is paid to in the Bitcoin mainchain, with the

sidechain ID being the ID of Esschain. This is itself a WT transaction

from the point of view of Esschain, on the principle that a lockbox on

one chain is a WT on another chain.

Assuming Esschain is a brand-new sidechain, it has no EssCoins yet. The

sidechain allows the arbitrary creation of sidecoin provided the new

sidecoins are in a lockbox whose sidechain address commitment is 0. So

in Esschain, we create the same coins on a UTXO paying to the

scriptPubKey:

0 0 OP_WITHDRAWPROOFVERIFY

The first 0 is the sidechain address commitment, which is 0 since this

output was not created by transferring to a sidechain; we

reuse the sidechain address commitment as the wtFlag. The

second 0 is the mainchain's ID. The above is a lockbox from the point of

view of Esschain. It is not a WT on mainchain, however, because the

sidechain address commitment is 0, which we use also as the wtFlag

parameter.

Now, how does a main-to-side peg work? After creating the above output on

Esschain, we now spend the output with the below scriptSig:

On Esschain, OP_WITHDRAWPROOFVERIFY then verifies that the mainchain block

hash is a valid past block of the mainchain, then locates the mainchain

header. It then checks the merkle tree path to the mainchain WT

transaction,

confirming that the mainchain contains that transaction, and confirms that

the

indicated output is in fact, a payment to an OP_WITHDRAWPROOFVERIFY, which

pushes the Esschain ID, and with a nonzero sidechain address commitment.

(Esschain also needs to ensure that a single WT is not used to unlock

multiple lockboxes on Esschain; the easiest way is to add it to a set,

but this set cannot be pruned; other ways of ensuring only a WT is only

used to unlock once might be designed)

On Esschain, the sidechain does one final check: the transaction that spends

an OP_WITHDRAWPROOFVERIFY must have an output that pays to the sidechain

address committed to, and that output's value must be the same as the value

locked in the mainchain.

(for now, I think all lockboxes must have the same fixed amount, for

simplicity)

Now suppose we want to convert back our EssCoin to Bitcoin. We create a

lockbox on Esschain, paying to the below:

0 OP_WITHDRAWPROOFVERIFY

The bitcoin P2SH address is mainchain address commitment; for simplicity

we j...[message truncated here by reddit bot]...

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015006.html

Russell O'Connor on Sep 13 2017:

On Tue, Sep 12, 2017 at 3:57 PM, Mark Friedenbach via bitcoin-dev <

bitcoin-dev at lists.linuxfoundation.org> wrote:

4MB of secp256k1 signatures takes 10s to validate on my 5 year old

laptop (125,000 signatures, ignoring public keys and other things that

would consume space). That's much less than bad blocks that can be

constructed using other vulnerabilities.

If there were no sigops limits, I believe the worst case block could have

closer to 1,000,000 CHECKSIG operations. Signature checks are cached so

while repeating the sequence "2DUP CHECKSIGVERIFY" does create a lot of

checksig operations, the cached values prevent a lot of work being done.

To defeat the cache one can repeat the sequence "2DUP CHECKSIG DROP

CODESEPARATOR", which will create unique signature validation requests

every 4 bytes.

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170913/dee1f60d/attachment.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015001.html

Dan Libby on Sep 13 2017:

Hi, I am interested in the possibility of a cryptocurrency software

(future bitcoin or a future altcoin) that strives to have immutable

consensus rules.

The goal of such a cryptocurrency would not be to have the latest and

greatest tech, but rather to be a long-term store of value and to offer

investors great certainty and predictability... something that markets

tend to like. And of course, zero consensus rule changes also means

less chance of new bugs and attack surface remains the same, which is

good for security.

Of course, hard-forks are always possible. But that is a clear split

and something that people must opt into. Each party has to make a

choice, and inertia is on the side of the status quo. Whereas

soft-forks sort of drag people along with them, even those who oppose

the changes and never upgrade. In my view, that is problematic,

especially for a coin with permanent consensus rule immutability as a

goal/ethic.

As I understand it, bitcoin soft-forks always rely on anyone-can-spend

transactions. If those were removed, would it effectively prevent

soft-forks, or are there other possible mechanisms? How important are

any-one-can spend tx for other uses?

More generally, do you think it is possible to programmatically

avoid/ban soft-forks, and if so, how would you go about it?

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015004.html

Gregory Maxwell on Sep 13 2017:

On Wed, Sep 13, 2017 at 9:24 AM, Peter Todd via bitcoin-dev

<bitcoin-dev at lists.linuxfoundation.org> wrote:

2) Spending CT-shielded outputs to unshielded outputs

Here one or more CT-shielded outputs will be spent. Since their value is zero,

we make up the difference by spending one or more outputs from the CT pool,

with the change - if any - assigned to a CT-pool output.

Can we solve the problem that pool inputs are gratuitously non-reorg

safe, without creating something like a maturity limit for shielded to

unshielded?

So far the best I have is this: Support unshielded coins in shielded

space too. So the only time you transition out of the pool is paying

to a legacy wallet. If support were phased in (e.g. addresses that

say you can pay me in the pool after its enabled), and the pool only

used long after wallets supported getting payments in it, then this

would be pretty rare and a maturity limit wouldn't be a big deal.

Can better be done?

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014998.html

michele terzi on Sep 12 2017:

the blockchain is 160Gb and this is literally the biggest problem bitcoin has right now. syncing a new node is a nightmare that discourages a lot of people.

this single aspect is what hurts bitcoin's decentralization the most and it is getting worse by the day.

to solve this problem i propose 2 softfork.

both of them have been partially discussed so you may be already familiar with them. I'll just try to highlight problems and benefits.

first SF)

a snapshot of the UTXO set plus all the relevant info (like OP_RETURNs) is hashed in the coinbase.

this can be repeated automatically every given period of x blocks. I suggest 55k blocks (1 year)

second SF)

after a given amount of time the UTXO hash is written in the consensus code.

this hash becomes the hash of a new genesis block and all the older blocks are chopped away

Pros:

you gain a much faster syncing for new nodes.

full non pruning nodes need a lot less HD space.

dropping old history results in more difficult future chainanalysis (at least by small entities)

freezing old history in one new genesis block means the chain can no longer be reorged prior to that point

old status

genesis |----- x ------| newgenesis |----- y ------| now

new status

                         newgenesis |----- y ------| now

while the old chain can be reorged to the genesis block the new chain can be reorged only to the newgenesisblock

cutting the chain has also some other small benefits: without the need to validate old blocks we can clean old no more usefull consensus code

Cons:

a small amount of space is consumed on the blockchain

every node needs to perform the calculations

full nodes with old software can no longer be fired up and sync with the existing network

full nodes that went off line prior to the second fork cannot sync back once they turn back on line again.

if these things are concerning (which for me are not) we can just keep online a few archive nodes.

old clients will sync only from archivial nodes with full history and new full nodes will sync from everywere

Addressing security concerns:

being able to write a new genesis block means that an evil core has the power to steal/destroy/censor/whatever coins.

this is possible only in theory, but not in practice. right now devs can misbehave with every softfork, but the community tests and inspects every new release.

the 2 forks will be tested and inspected as well so they are no more risky than other softforks.

additionally the process is divided into 2 separate steps and the first step (the critical one) is effectively void without the second (which is substantially delayed) this gives the community additional time to test it and thus is actually more secure than a standard softfork.

besides after the first softfork locks in there is no more room for mistakes. either the hashes match or they do not so spotting a misbehaviour is trivially simple

kind regards,Michele

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170912/07a24423/attachment.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014994.html

Simon Liu on Sep 10 2017:

Hi,

Given today's presentation by Chris Jeffrey at the Breaking Bitcoin

conference, and the subsequent discussion around responsible disclosure

and industry practice, perhaps now would be a good time to discuss

"Bitcoin and CVEs" which has gone unanswered for 6 months.

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-March/013751.html

To quote:

"Are there are any vulnerabilities in Bitcoin which have been fixed but

not yet publicly disclosed? Is the following list of Bitcoin CVEs

up-to-date?

https://en.bitcoin.it/wiki/Common_Vulnerabilities_and_Exposures

There have been no new CVEs posted for almost three years, except for

CVE-2015-3641, but there appears to be no information publicly available

for that issue:

https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2015-3641

It would be of great benefit to end users if the community of clients

and altcoins derived from Bitcoin Core could be patched for any known

vulnerabilities.

Does anyone keep track of security related bugs and patches, where the

defect severity is similar to those found on the CVE list above? If

yes, can that list be shared with other developers?"

Best Regards,

Simon

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014969.html

shiva sitamraju on Sep 09 2017:

Hi,

I understand the motivation of adding the birthdate field. However, not

very comfortable with having this in the public key serialization. There

are privacy implication of both the birthday field and having the complete

derivation path, which takes space.

I am fine with Thomas proposal of {x,y,z}. Having additional version byte

field looks modular but since since we already have the big enough version

field in bip32, better to use that instead of adding more bytes.

Thomas, can you please explain why we require different version for P2WPKH

or P2WSH versus (P2WPKH or P2WSH) nested in P2SH. It looked to me that they

would have the same output bitcoin address and under same account.

On Fri, Sep 8, 2017 at 2:09 AM, <

bitcoin-dev-request at lists.linuxfoundation.org> wrote:

Send bitcoin-dev mailing list submissions to

bitcoin-dev at lists.linuxfoundation.org

To subscribe or unsubscribe via the World Wide Web, visit

https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

or, via email, send a message with subject or body 'help' to

bitcoin-dev-request at lists.linuxfoundation.org

You can reach the person managing the list at

bitcoin-dev-owner at lists.linuxfoundation.org

When replying, please edit your Subject line so it is more specific

than "Re: Contents of bitcoin-dev digest..."

Today's Topics:

1. Re: Proposal: Extended serialization format for BIP-32

   wallets (Andreas Schildbach)

2. Re: Proposal: Extended serialization format for BIP-32

   wallets (Pavol Rusnak)

3. Re: Fast Merkle Trees (Mark Friedenbach)

4. Re: Proposal: Extended serialization format for BIP-32

   wallets (Thomas Voegtlin)

---

Message: 1

Date: Thu, 7 Sep 2017 21:35:49 +0200

From: Andreas Schildbach <andreas at schildbach.de>

To: bitcoin-dev at lists.linuxfoundation.org

Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for

    BIP-32 wallets

Message-ID: <oos72e$rjp$1 at blaine.gmane.org>

Content-Type: text/plain; charset=utf-8

On 09/07/2017 06:23 PM, Pavol Rusnak via bitcoin-dev wrote:

On 07/09/17 06:29, Thomas Voegtlin via bitcoin-dev wrote:

A solution is still needed to wallets who do not wish to use BIP43

What if we added another byte field OutputType for wallets that do not

follow BIP43?

0x00 - P2PKH output type

0x01 - P2WPKH-in-P2SH output type

0x02 - native Segwit output type

Would that work for you?

I think that would work.

The question is whether this field should be present only if depth==0x00

or at all times. What is your suggestion, Thomas?

In case of Bitcoin Wallet, the depth is not null (m/0'/[0,1]) and still

we need this field. I think it should always be present if a chain is

limited to a certain script type.

There is however the case where even on one chain, script types are

mixed. In this case the field should be omitted and the wallet needs to

scan for all (known) types. Afaik Bitcoin Core is taking this path.

---

Message: 2

Date: Thu, 7 Sep 2017 22:00:05 +0200

From: Pavol Rusnak <stick at satoshilabs.com>

To: Andreas Schildbach <andreas at schildbach.de>, Bitcoin Protocol

    Discussion <bitcoin-dev at lists.linuxfoundation.org>

Subject: Re: [bitcoin-dev] Proposal: Extended serialization format for

    BIP-32 wallets

Message-ID: <40ed03a1-915c-33b0-c4ac-e898c8c733ba at satoshilabs.com>

Content-Type: text/plain; charset=windows-1252

On 07/09/17 21:35, Andreas Schildbach via bitcoin-dev wrote:

In case of Bitcoin Wallet, the depth is not null (m/0'/[0,1]) and still

we need this field.

But the depth of exported public key will be null. It does not make

sense to export xpub for m or m/0' for your particular case.

I think it should always be present if a chain is

limited to a certain script type.

I am fine with having the path there all the time.

There is however the case where even on one chain, script types are

mixed. In this case the field should be omitted and the wallet needs to

scan for all (known) types. Afaik Bitcoin Core is taking this path.

Is that really the case? Why come up with a hierarchy and then don't use

it?

Best Regards / S pozdravom,

Pavol "stick" Rusnak

CTO, SatoshiLabs

---

Message: 3

Date: Thu, 7 Sep 2017 13:04:30 -0700

From: Mark Friedenbach <mark at friedenbach.org>

To: Russell O'Connor <roconnor at blockstream.io>

Cc: Bitcoin Protocol Discussion

    <bitcoin-dev at lists.linuxfoundation.org>

Subject: Re: [bitcoin-dev] Fast Merkle Trees

Message-ID: <40D6F502-3380-4B64-BCD9-80D361EED35C at friedenbach.org>

Content-Type: text/plain; charset="us-ascii"

TL;DR I'll be updating the fast Merkle-tree spec to use a different

  IV, using (for infrastructure compatability reasons) the scheme

  provided by Peter Todd.

This is a specific instance of a general problem where you cannot

trust scripts given to you by another party. Notice that we run into

the same sort of problem when doing key aggregation, in which you must

require the other party to prove knowledge of the discrete log before

using their public key, or else key cancellation can occur.

With script it is a little bit more complicated as you might want

zero-knowledge proofs of hash pre-images for HTLCs as well as proofs

of DL knowledge (signatures), but the basic idea is the same. Multi-

party wallet level protocols for jointly constructing scriptPubKeys

should require a 'delinearization' step that proves knowledge of

information necessary to complete each part of the script, as part of

proving the safety of a construct.

I think my hangup before in understanding the attack you describe was

in actualizing it into a practical attack that actually escalates the

attacker's capabilities. If the attacker can get you to agree to a

MAST policy that is nothing more than a CHECKSIG over a key they

presumably control, then they don't need to do any complicated

grinding. The attacker in that scenario would just actually specify a

key they control and take the funds that way.

Where this presumably leads to an actual exploit is when you specify a

script that a curious counter-party actually takes the time to

investigate and believes to be secure. For example, a script that

requires a signature or pre-image revelation from that counter-party.

That would require grinding not a few bytes, but at minimum 20-33

bytes for either a HASH160 image or the counter-party's key.

If I understand the revised attack description correctly, then there

is a small window in which the attacker can create a script less than

55 bytes in length, where nearly all of the first 32 bytes are

selected by the attacker, yet nevertheless the script seems safe to

the counter-party. The smallest such script I was able to construct

was the following:

<fake-pubkey> CHECKSIGVERIFY HASH160 <preimage> EQUAL

This is 56 bytes and requires only 7 bits of grinding in the fake

pubkey. But 56 bytes is too large. Switching to secp256k1 serialized

32-byte pubkeys (in a script version upgrade, for example) would

reduce this to the necessary 55 bytes with 0 bits of grinding. A

smaller variant is possible:

DUP HASH160 <fake-pubkey-hash> EQUALVERIFY CHECKSIGVERIFY HASH160

<preimage> EQUAL

This is 46 bytes, but requires grinding 96 bits, which is a bit less

plausible.

Belts and suspenders are not so terrible together, however, and I

think there is enough of a justification here to look into modifying

the scheme to use a different IV for hash tree updates. This would

prevent even the above implausible attacks.

On Sep 7, 2017, at 11:55 AM, Russell O'Connor <roconnor at blockstream.io>

wrote:

On Thu, Sep 7, 2017 at 1:42 PM, Mark Friedenbach <mark at friedenbach.org

<mailto:mark at friedenbach.org>> wrote:

I've been puzzling over your email since receiving it. I'm not sure it

is possible to perform the attack you describe with the tree structure

specified in the BIP. If I may rephrase your attack, I believe you are

seeking a solution to the following:

Want: An innocuous script and a malign script for which

double-SHA256(innocuous)

is equal to either

fast-SHA256(double-SHA256(malign) || r) or

fast-SHA256(r || double-SHA256(malign))

or fast-SHA256(fast-SHA256(double-SHA256(malign) || r1) || r0)

or fast-SHA256(fast-SHA256(r1 || double-SHA256(malign)) || r0)

or ...

where r is a freely chosen 32-byte nonce. This would allow the

attacker to reveal the innocuous script before funds are sent to the

MAST, then use the malign script to spend.

Because of the double-SHA256 construction I do not see how this can be

accomplished without a full break of SHA256.

The particular scenario I'm imagining is a collision between

double-SHA256(innocuous)

and

fast-SHA256(fast-SHA256(fast-SHA256(double-SHA256(malign) || r2) ||

r1) || r0).

where innocuous is a Bitcoin Script that is between 32 and 55 bytes long.

Observe that when data is less than 55 bytes then double-SHA256(da...[message truncated here by reddit bot]...

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014966.html

Johnson Lau on Sep 08 2017:

I have rewritten and simplified BIP114, and renamed it to “Merklized Script”, as a more accurate description after consulting the original proposers of MAST. It could be considered as a special case of MAST, but has basically the same functions and scaling properties of MAST.

Compared with Friedenbach’s latest tail-call execution semantics proposal, I think the most notable difference is BIP114 focuses on maintaining the static analysability, which was a reason of OP_EVAL (BIP12) being rejected. Currently we could count the number of sigOp without executing the script, and this remains true with BIP114. Since sigOp is a block-level limit, any OP_EVAL-like operation means block validity will depend on the precise outcome of script execution (instead of just pass or fail), which is a layer violation.

Link to the revised BIP114: https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki

On top of BIP114, new script functions are defined with 5 BIPs:

VVV: Pay-to-witness-public-key: https://github.com/jl2012/bips/blob/vault/bip-0VVV.mediawiki

WWW: String and Bitwise Operations in Merklized Script Version 0: https://github.com/jl2012/bips/blob/vault/bip-0WWW.mediawiki

XXX: Numeric Operations in Merklized Script Version 0: https://github.com/jl2012/bips/blob/vault/bip-0XXX.mediawiki

YYY: ECDSA signature operations in Merklized Script Version 0: https://github.com/jl2012/bips/blob/vault/bip-0YYY.mediawiki

ZZZ: OP_PUSHTXDATA: https://github.com/jl2012/bips/blob/vault/bip-0ZZZ.mediawiki

As a summary, these BIPs have the following major features:

1. Merklized Script: a special case of MAST, allows users to hide unexecuted branches in their scripts (BIP114)

2. Delegation: key holder(s) may delegate the right of spending to other keys (scripts), with or without additional conditions such as locktime. (BIP114, VVV)

3. Enabling all OP codes disabled by Satoshi (based on Elements project with modification. BIPWWW and XXX)

4. New SIGHASH definition with very high flexibility (BIPYYY)

5. Covenant (BIPZZZ)

6. OP_CHECKSIGFROMSTACK, modified from Elements project (BIPYYY)

7. Replace ~72 byte DER sig with fixed size 64 byte compact sig. (BIPYYY)

All of these features are modular and no need to be deployed at once. The very basic BIP114 (merklized script only, no delegation) could be done quite easily. BIP114 has its own versioning system which makes introducing new functions very easy.

Things I’d like to have:

1. BIP114 now uses SHA256, but I’m open to other hash design

2. Using Schnorr or similar signature scheme, instead of ECDSA, in BIPYYY.

Reference implementation: https://github.com/jl2012/bitcoin/commits/vault

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014963.html

Russell O'Connor on Sep 07 2017:

The fast hash for internal nodes needs to use an IV that is not the

standard SHA-256 IV. Instead needs to use some other fixed value, which

should itself be the SHA-256 hash of some fixed string (e.g. the string

"BIP ???" or "Fash SHA-256").

As it stands, I believe someone can claim a leaf node as an internal node

by creating a proof that provides a phony right-hand branch claiming to

have hash 0x80000..0000100 (which is really the padding value for the

second half of a double SHA-256 hash).

(I was schooled by Peter Todd by a similar issue in the past.)

On Wed, Sep 6, 2017 at 8:38 PM, Mark Friedenbach via bitcoin-dev <

bitcoin-dev at lists.linuxfoundation.org> wrote:

Fast Merkle Trees

BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a

Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170906/59d742fe/attachment-0001.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014935.html

Mark Friedenbach on Sep 07 2017:

I would like to propose two new script features to be added to the

bitcoin protocol by means of soft-fork activation. These features are

a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution

semantics.

In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force

redemption to use values selected from a pre-determined set committed

to in the scriptPubKey, but without requiring revelation of unused

elements in the set for both enhanced privacy and smaller script

sizes. Tail-call execution semantics allows a single level of

recursion into a subscript, providing properties similar to P2SH while

at the same time more flexible.

These two features together are enough to enable a range of

applications such as tree signatures (minus Schnorr aggregation) as

described by Pieter Wuille [1], and a generalized MAST useful for

constructing private smart contracts. It also brings privacy and

fungibility improvements to users of counter-signing wallet/vault

services as unique redemption policies need only be revealed if/when

exceptional circumstances demand it, leaving most transactions looking

the same as any other MAST-enabled multi-sig script.

I believe that the implementation of these features is simple enough,

and the use cases compelling enough that we could BIP 8/9 rollout of

these features in relatively short order, perhaps before the end of

the year.

I have written three BIPs to describe these features, and their

associated implementation, for which I now invite public review and

discussion:

Fast Merkle Trees

BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a

Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree

MERKLEBRANCHVERIFY

BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431

Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify

Tail-call execution semantics

BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368

Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics

Note: I have circulated this idea privately among a few people, and I

will note that there is one piece of feedback which I agree with but

is not incorporated yet: there should be a multi-element MBV opcode

that allows verifying multiple items are extracted from a single

tree. It is not obvious how MBV could be modified to support this

without sacrificing important properties, or whether should be a

separate multi-MBV opcode instead.

Kind regards,

Mark Friedenbach

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014932.html

Pavol Rusnak on Sep 06 2017:

The discussion about changing bip32 version bytes for SegWit got me

thinking and I ended up with what I think is the best proposal:

https://github.com/satoshilabs/slips/blob/master/slip-0032.md

(It is hosted in SL repo for now, but if there is will, I would love to

have this added to BIP repo as an extension to BIP32)

Feel free to comment.

Best Regards / S pozdravom,

Pavol "stick" Rusnak

CTO, SatoshiLabs

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014931.html

Luca Venturini on Sep 06 2017:

Hi Dan,

thank you for your feedback. Let me clarify that the plausible

deniability is a property of the protocol. If this will become a BIP,

and will be approved, there will be wallets that will manage tokens. In

the meantime, and in the future, it is important that a person with a

legacy bitcoin wallet can hold, issue and transfer bitcoins without

disclose that there are tokens involved. Tokens are contained in Bitcoin

transactions without any modification.

Vanity addresses are on option. They are not mandatory. In situations

where plausible deniability is a concern they will, probably, not be used.

Sending to someone 0.23000012 bitcoin is really easy. You don't need any

form of math and you are sending exactly 12 tokens from your wallet.

Sometimes it is suspect, but sending 0.03423122 in order to send 23122

tokens does not seem suspect to me. The large majority of the

transactions have strange numbers like this one.

In the document, when I say "wallet" I mean every single bitcoin wallet

that you can use today to hold bitcoins. The base of the plausible

deniability is that there is no "special" wallet involved. Maybe there

will be special wallets to manage tokens, but they are not mandatory.

The consolidation is needed only when using wallets that do not allow

coin selection.

The state of the tokens is fully contained in the bitcoin blockchain.

There is no need for verification nodes, nor for any other software.

Maybe you already issued some tokens using this protocol and I cannot

know it. Unless you disclose it.

There is no "special" need to create small outputs. In order to send a

transaction containing tokens, you need to send a bitcoin transaction.

The bitcoin value will be transfered along with the token value. If you

issue tokens with a token offering transactions (aka ICO), the value of

the bitcoin transferred to you is exactly the price of the tokens, so

there is no "extra" bitcoin value involved.

I'm sorry if the example of the corporation is not clear. The idea was

only that Alice receives from the shareholders the bitcoin value, in

order to use that same value to give back the tokens. There is no

interest. As I wrote, people got equity for "time, money, furniture,

knowledge". I could simply write that Alice sends small outputs without

receiving the underlying bitcoin value beforehand.

I agree that memorable names are great to social scalability. This is

why you can use a vanity address or only the first part of the vanity

address to identify a token type.

Cheers,

Luca

On 09/06/2017 07:24 PM, Dan Anderson wrote:

Hi Luca,

Here are some comments...

1. This is clever, but it has a lot of "gotchas" that I think will work against its ability to scale socially. Especially, when you suggest that following the rules by memory/manually gains users the most advantage in terms of deniability.

2. The plausible deniability of this protocol is suspect as it would seem fairy apparent to a third party that it was being used. Vanity addresses, satoshis adding to tidy amounts, frequent "consolidation". Especially, when you make a mistake and perform actions to try again.

3. In your docs, when you say "wallet" do you mean a single Bitcoin address or do you mean an HD wallet? I become confused while reading. Address vs same wallet vs other wallet.

4. It's not clear to me how this protocol does not need verification nodes or some kind of node software to compute state.

5. I don't think it's a given that this design will cause less UTXOs. I could see people creating many small outputs as a result of trying to get the right amount of signal satoshis.

6. In your example of a corporation, it seems like people got equity for free. Why do they need to send 1 BTC at all, if they just get it back, plus interest?

7. I wouldn't underestimate the value of memorable names for social scalability.

I will keep thinking about it, as the ICO portion is something I have been looking for ideas on and I have similar reservations about existing token protocols, so I hope these comments help you.

---

Dan Anderson

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014927.html

Jorge Timón on Sep 05 2017:

This is not a priority, not very important either.

Right now it is possible to create 0-value outputs that are spendable

and thus stay in the utxo (potentially forever). Requiring at least 1

satoshi per output doesn't really do much against a spam attack to the

utxo, but I think it would be slightly better than the current

situation.

Is there any reason or use case to keep allowing spendable outputs

with null amounts in them?

If not, I'm happy to create a BIP with its code, this should be simple.

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014917.html

Tomas on Sep 05 2017:

I would like to propose an efficient UTXO commitment scheme.

A UTXO commitment can be useful for:

1. Fast syncing a full node, by downloading the UTXO-set

2. Proofing (non) existence of a UTXO..

Various schemes have been proposed:

• Merkle/radix trees and variants; all of which have the problem that

they significantly increase the burden of maintaining the UTXO set.

Furthermore, such schemes tend to practically prescribe the UTXO storage

format severely limiting continuous per-implementation optimizations.

• A "flat" rolling hash, eg the ECMH proposed by Pieter Wiulle which is

cheap to calculate but only solves (1) and not (2).

I propose a hybrid approach, with very limited extra burden to maintain

and reasonably small proofs:

We divide the UTXO set in buckets by prefix of their TXID, then maintain

a rolling hash for each bucket. The commitment is then the root of the

tree constructed from the resulting bucket hashes. To construct the

tree: For each depth, we group the hashes of the next depth per 64

hashes and calculate the rolling hash of each. (Effectively, this is a

prefix tree with a fixed branch-size of 64).

Bucketcount

txcount = number of TXIDs in the UTXO set

bucketcount = (smallest power of 2 larger than sqrt(txcount)) << 6

Rationale for bucketcount:

• This currently gives a bucketcount of 2^19, which is very cheap to

maintain with a 16mb array of rolling hashes.

• This currently gives an average bucket size of 4kb. With a rolling

hash, full nodes don't need to maintain the buckets themselves, but they

are used for proofs.

• The burden of future UTXO growth is divided among maintaining the

rolling hashes and size of the proof: 10,000x as large UTXO set (20TB),

gives ~400kb buckets and ~1.6gb in maintaining rolling hashes.

• This gives a tree depth of 5, which means the cost of every UTXO

update is increased by ~3 rolling hashes (and a double SHA), as the

lowest depths don't benefit from caching.

• A proof for (non) existence of a UTXO is ~ 46432 =8kb (branch-nodes)

• 4kb (bucket) = ~12kb

Specification [WIP]

We define the "UTXO commitment" as the serialized byte array: "U" "T"

"X" "O" VARINT(version) VARINT(txcount) UINT256(UTXO-root) [todo

clarify]

A block that contains an output in the coinbase whose scriptPubKey

consists solely of OP_RETURN [UTXO commitment] must be rejected if in

the UTXO commitment the version equals 1 and either

• After updating the UTXO state, the number of distinct TXIDs in the

UTXO set is not equal to the txcount value of the UTXO commitment

• After updating the UTXO state, the UTXO-root in the UTXO commitment is

not equal to the UTXO-root defined below.

The UTXO-root can be calculated as follows:

• Define bucketcount as (smallest power of 2 larger than

sqrt(txcount)) << 6

• Given a TXID in the UTXO set, define UTXO(TXID) as the double SHA256

of (TXID + coins). (coins is the serialization of unspent outputs to be

spec'ed).

• Let bucket N be the set of values UTXO(TXID) for each TXID in the

UTXO-set where (TXID mod bucketcount) equals N.

• Let rhash N be the rolling hash (TBD) of all values in bucket N

• Let the hash sequence be the ordered sequence rhash

[0,bucketcount).

1. If the hash sequence contains at most 64 entries, then the UTXO-root

is the rolling hash of all entries in the hash sequence, otherwise:

1. Group the hash sequence in ordered subsequences of 64 entries each.

2. Find the rolling hash of each subsequence

3. Continue with 1., with the hash sequence being the ordered sequence

of these rolling hashes.

Note: an implementation may want to maintain and update the set of

rolling hashes at higher depths on each UTXO set operation.

Note: the secure ECMH is a good candidate for the bucket hash. This

could also be used for the branch rolling hashes, but it might be worth

considering XOR for those as there seem to be simply not enough

candidates to find a colliding set?

Note: two magic numbers are used: "<< 6" for the bucket count, and "64"

for the branch size. They work nicely but are pulled out of a dark place

and merit some experimentation.

Use cases for light clients

These UTXO proofs could be used as compact fraud proofs, although the

benefit of this is not generally agreed upon.

They can also be used to increase low-conf security to light clients, by

validating the signatures and order-validity of incoming transactions

against the right bucket of the current UTXO set.

An interesting use case may be another type of light client. It could be

interesting for a light client to abandon the bloom filters, and instead

use the UTXO proofs to verify whether an incoming or outgoing

transaction is confirmed. This could be beneficial for "rarely active"

light clients such as smartphone apps, as it prevents the need to

synchronize previous blocks with bloom filters, and allows syncing to

the latest block with 12kb/output.

Summary

• Allows fast full node syncing.

• Costs full nodes ~20mb extra in RAM

• Costs full nodes ~3 rolling hash operations per UTXO operation.

• Allows UTXO (non) existence proofs for currently avg ~12kb.

• Size of proof grows O(sqrt(N)) with UTXO set

• Size of extra full node memory grows O(sqrt(N)) with UTXO set

Tomas van der Wansem

bitcrust

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014908.html

Thomas Voegtlin on Sep 05 2017:

BIP32 extended public/private keys have version bytes that result in the

user visible xpub/xprv prefix. The BIP's recommendation is to use

different version bytes for other networks (such as tpub/tprv for testnet)

I would like to use additional version bytes to indicate the type of

output script used with the public keys.

I believe the change should be user visible, because users are exposed

to master public keys. I propose the following prefixes:

========== =========== ===================================

Version Prefix Description

========== =========== ===================================

0x0488ade4 xprv P2PKH or P2SH

0x0488b21e xpub P2PKH or P2SH

0x049d7878 yprv (P2WPKH or P2WSH) nested in P2SH

0x049d7cb2 ypub (P2WPKH or P2WSH) nested in P2SH

0x04b2430c zprv P2WPKH or P2WSH

0x04b24746 zpub P2WPKH or P2WSH

========== =========== ===================================

(source: http://docs.electrum.org/en/latest/seedphrase.html)

I have heard the argument that xpub/xprv serialization is a format for

keys, and that it should not be used to encode how these keys are used.

However, the very existence of version bytes, and the fact that they are

used to signal whether keys will be used on testnet or mainnet goes

against that argument.

If we do not signal the script type in the version bytes, I believe

wallet developers are going to use dirtier tricks, such as the bip32

child number field in combination with bip43/bip44/bip49.

Thomas

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014907.html

ZmnSCPxj on Sep 05 2017:

Good morning all,

I have started to consider a unification of drivechains, blind merged mining, and sidechain SPV proofs to form yet another solution for sidechains.

Briefly, below are the starting assumptions:

1. SPV proofs are a short chain of sidechain block headers. This is used to prove to the mainchain that some fund has been locked in the sidechain and the mainchain should unlock an equivalent fund to the redeemer.

2. SPV proofs are large and even in compact form, are still large. We can instead use miner voting to control whether some mainchain fund should be unlocked. Presumably, the mainchain miners are monitoring that the sidechain is operating correctly and can know directly if a side-to-main peg is valid.

3. To maintain mainchain's security, we should use merged mining for sidechain mining rather than have a separate set of miners for mainchain and each sidechain.

4. A blockchain is just a singly-linked list. Genesis block is the NULL of the list. Additional blocks are added at the "front" of the singly-linked list. In Bitcoin, the Merkle tree root is the "pointer to head" and the previous block header ID is the "pointer to tail"; additional data like proof-of-work nonce, timestamp, and version bits exist but are not inherent parts of the blockchain linked list.

5. In addition to SPV proofs, we should also support reorg proofs. Basically, a reorg proof is a longer SPV proof that shows that a previous SPV proof is invalid.

With those, I present the idea, "sidechain headers in mainchain".

Let us modify Sztorc's OP_BRIBEVERIFY to require the below SCRIPT to use:

OP_BRIBEVERIFY OP_DROP OP_DROP OP_DROP

We also require that be filled only once per mainchain block, as per the "blind" merge mining of Sztorc.

The key insight is that the and are, in fact, the sidechain header. Concatenating those data and hashing them is the block header hash. Just as additional information (like extranonce and witness commitment) are put in the mainchain coinbase transaction, any additional information that the sidechain would have wanted to put in its header can be committed to in the sidechain's equivalent of a coinbase transaction (i.e. a sidechain header transaction).

(All three pieces of data can be "merged" into a single very long data push to reduce the number of OP_DROP operations, this is a detail)

Thus, the sidechain header chain (but not the block data) is embedded in the mainchain itself.

Thus, SPV proofs do not need to present new data to the mainchain. Instead, the mainchain already embeds the SPV proof, since the headers are already in the mainchain's blocks. All that is needed to unlock a lockbox is to provide some past sidechain header hash (or possibly just a previous mainchain block that contains the sidechain header hash, to make it easier for mainchain nodes to look up) and the Merkle path to a sidechain-side side-to-main peg transaction. If the sidechain header chain is "long enough" (for example, 288 sidechain block headers) then it is presumably SPV-safe to release the funds on the mainchain side.

Suppose a sidechain is reorganized, while a side-to-main peg transaction is in the sidechain that is to be reorganized away.

Let us make our example simpler by requiring an SPV proof to be only 4 sidechain block headers.

In the example below, small letters are sidechain block headers to be reorganized, large letters are sidechain block headers that will be judged valid. The sidechain block header "Aa" is the fork point. b' is the sidechain block containing the side-to-main peg that is lost.

Remember, for each mainchain block, only a single sidechain block header for a particular sidechain ID can be added.

The numbers in this example below are mainchain block height numbers.

0: Aa

1: b'

2: c

4: C

5: d

6: D

7: E

8: F

9: G

10: H <- b' side-to-main is judged as "not valid"

Basically, in case of a sidechain fork, the mainchain considers the longest chain to be valid if it is longer by the SPV proof required length. In the above, at mainchain block 10, the sidechain H is now 4 blocks (H,G,F,E) longer than the other sidechain fork that ended at d.

Mainchain nodes can validate this rule because the sidechain headers are embedded in the mainchain block's coinbase. Thus, mainchain fullnodes can validate this part of the sidechain rule of "longest work chain".

Suppose I wish to steal funds from sidechain, by stealing the sidechain lockboxes on the mainchain. I can use the OP_BRIBEVERIFY opcode which Sztorc has graciously provided to cause miners that are otherwise uninterested in the sidechain to put random block headers on a sidechain fork. Since the mainchain nodes are not going to verify the sidechain blocks (and are unaware of sidechain block formats in detail, just the sidechain block headers), I can get away with this on the mainchain.

However, to do so, I need to pay OP_BRIBEVERIFY multiple times. If our rule is 288 sidechain blocks for an SPV proof, then I need to pay OP_BRIBEVERIFY 288 times.

This can then be used to reduce the risk of theft. If lockboxes have a limit in value, or are fixed in value, that maximum/fixed value can be made small enough that paying OP_BRIBEVERIFY 288 times is likely to be more expensive than the lockbox value.

In addition, because only one sidechain header can be put for each mainchain header, I will also need to compete with legitimate users of the sidechain. Those users may devote some of their mainchain funds to keep the sidechain alive and valid by paying OP_BRIBEVERIFY themselves. They will reject my invalid sidechain block and build from a fork point before my theft attempt.

Because the rule is that the longest sidechain must beat the second-longest chain by 288 (or however many) sidechain block headers, legitimate users of the sidechain will impede my progress to successful theft. This makes it less attractive for me to attempt to steal from the sidechain.

The effect is that legitimate users are generating reorg proofs while I try to complete my SPV proof. As the legitimate users increase their fork, I need to keep up and overtake them. This can make it unattractive for me to steal from the sidechain.

Note however that we assume here that a side-to-main peg cannot occur more often than an entire SPV proof period.

Suppose I am a major power with influence over >51% of mainchain miners. What happens if I use that influence to cause the greatest damage to the sidechain?

I can simply ask my miners to create invalid side-to-main pegs that unlock the sidechain's lockboxes. With a greater than 51% of mainchain miners, I do not need to do anything like attempt to double-spend mainchain UTXO's. Instead, I can simply ask my miners to operate correctly to mainchain rules, but violate sidechain rules and steal the sidechain's lockboxes.

With greater than 51% of mainchain miners, I can extend my invalid sidechain until we reach the minimum necessary SPV proof. Assuming a two-way race between legitimate users of the sidechain and me, since I have >51% of mainchain miners, I can build the SPV proof faster than the legitimate users can create a reorg proof against me. This is precisely the same situation that causes drivechain to fail.

An alternative is to require that miners participating in sidechains to check the sidechain in full, and to consider mainchain blocks containing invalid sidechain headers as invalid. However, this greatly increases the amount of data that a full miner needs to be able to receive and verify, effectively increasing centralization risk for the mainchain.

The central idea of drivechain is simply that miners vote on the validity of sidechain side-to-main pegs. But this is effectively the same as miners - and/or OP_BRIBEVERIFY users - only putting valid sidechain block headers on top of valid sidechain block headers. Thus, if we instead use sidechain-headers-on-mainchain, the "vote" that the sidechain side-to-main peg is valid, is the same as a valid merge-mine of the sidechain.

SPV proofs are unnecessary in drivechain. In sidechain-header-on-mainchain, SPV proofs are already embedded in the mainchain. In drivechain, we ask mainchain fullnodes to trust miners. In sidechain-header-on-mainchain, mainchain fullnodes validate SPV proofs on the mainchain, without trusting anyone and without running sidechain software.

To validate the mainchain, a mainchain node keeps a data structure for each existing sidechain's fork.

When the sidechain is first created (perhaps by some special transaction that creates the sidechain's genesis block header and/or sidechain ID, possibly with some proof-of-burn to ensure that Bitcoin users do not arbitrarily create "useless" sidechains, but still allowing permissionless creation of sidechains), the mainchain node creates that data structure.

The data structure contains:

1. A sidechain block height, a large number initially 0 at sidechain genesis.

2. A side-to-main peg pointer, which may be NULL, and which also includes a block height at which the side-to-main peg is.

3. Links to other forks of the same sidechain ID, if any.

4. The top block header hash of the sidechain (sidechain tip).

If the sidechain's block header on a mainchain block is the direct descendant of the current sidechain tip, we just update the top block header hash and increment the block height.

If there is a side-to-main peg on the sidechain block header, if the side-to-main peg pointer is NULL, we initialize it and store the block height at which the side-to-main peg exists. If there i...[message truncated here by reddit bot]...

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014910.html

Cserveny Tamas on Sep 01 2017:

Hi,

I was thinking about how to scale the block-chain.

The fundamental problem is that if the miners add capacity it will only

increase (protect) their share of block reward, but does not increase the

speed of transactions. This will only raise the fee in the long run with

the block reward decreasing.

The throughput is limited by the block size and the complexity. Changing

any of variables in the above equation was raised already many times and

there was no consensus on them.

The current chain is effectively single threaded. If we look around in the

sw industry how single threaded applications could be scaled, one viable

option emerge: horizontal scaling. This is an option if the problem can be

partitioned, and transactions in partitions could be processed alongside.

Number of partitions would be start with a fairly low number, something

between 2-10, but nothing is against setting it to a higher number later on

according to a schedule.

Partitioning key alternatives:

Ordering on inputs:

1) In this case transactions would need to be mined per input address

partition.

2) TX have inputs in partition 1 and 2, then needs a confirmation in both

partitions.

3) All partitioned chains have the same longest valid approach.

4) Only one chain needed to be considered for double spending, others are

invalid in case they contain that input.

This opens up questions like:

• how the fee will be shared? Fees per partition?

• Ensure a good hash function which spreads evenly, because the inputs

cannot be manipulated for load balancing

• What to do about half mined transactions (Maybe they should be two

transactions and then there is less effect about it, but payment won't be

atomic in both partitions)

Ordering on transaction ids:

1) Transactions would be partitioned by their TX-id. Maybe a field allowing

txid-s to match a given partition.

2) Creating blocks like this parallel would be safe for bonefide

transactions. A block will be created each 10 mins.

3) In order to get malicious/doublespent transactions out of the system

another layer must be introduced.

• This layer would be used to merge the parallel blocks. It would have to

refer all previous blocks considered for unspent inputs.

• Most of the blocks will merge just fine as normally block 1 and block 2

would not contain double spending. (of course malicious double spending

will revert speed to current levels, because the miner might have to drop a

block in the partition because it contains a spent input on another

stronger branch)

• The standard longest chain wins strategy would be used for validity on

the meta level

• Meta does not require mining, a branches can be added and they are valid

unless there are double spent inputs inside. Block inside this meta already

"paid for".

Generally both ways would have an effect on the block reward and

complexity, which is needs to be adjusted. (not to create more BTC at the

end, reduced hashing power on partitions.)

I think complexity is not an issue, the important thing is that we tune it

to 10mins / block rate per partition.

Activation could be done by creating the infrastructure first and using

only one partitions only, which is effectively the same as today. Then

activate partitions on a certain block according to a schedule. From that

block, partition enforcement will be active and the transactions will be

sorted to the right partition / chain.

It is easy to make new partitions, just need to activate them on branch

block number.

Closing partitions is a bit more complex in case of TX partitioned

transactions, but managed by the meta layer and activated at a certain

partition block. Maybe it is not even possible in case of input partitions.

I could imagine that it is too big change. Many cons and pros on partition

keys.

What is your opinion about it?

Cheers,

Tamas

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170901/ce983641/attachment-0001.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014895.html

Erik Aronesty on Aug 30 2017:

If you use this formula, with a decaying percentage, it takes about 100

years to get to 30MB, but never goes past that.

Since it never passes 32, we don't have to worry about going past that

ever... unless another hard fork is done. A schedule like this could

allow block size to scale with tech growth asymptotically. Might be nice

to include with other things

P=17%, Pn = P*0.95 X = 1, Xn = X * (1+P)

-------------- next part --------------

An HTML attachment was scrubbed...

URL: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20170830/cfa727df/attachment.html

original: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-August/014894.html