Something similar to what you proposed can actually work.

It's called MAVEPAY (https://bitslog.wordpress.com/2012/04/16/mavepay-a-new-lightweight-payment-scheme-for-peer-to-peer-currency-networks/), and the signature protocol is called MAVE (https://bitslog.wordpress.com/2012/04/09/mave-digital-signature-protocol-for-massive-bulk-verifications/)

A weaker and later alternative was called FawkesCoin.

Fermat project is super cool. Luis showed me the platform preview some time ago and it looked solid. Keep an eye on Fermat, or better, participate in it!

Regards,
Sergio.

Where did you get that "he must have entered the hospital for his final stay around April, 2010" ?

Isn't that private information?

I will add some reasoning about free start pre-image / collisions attacks that makes me think it is less of a problem for this particular use. These are the reasons:

1. The security of pre-image resistance of SHA-256 in bits is 256 bits. If SHA-256 were 100% secure, an attacker that wants to reuse the PoW of another merge-mined block will need to perform 2^256 operations.  This attack will never be practical for SHA-256, even having a free start. There has be no successful practical pre-image attack to any of the once standardized hash functions (including MD5, SHA-1, etc.). The best theoretical pre-image attack to the broken MD5 requires 2^125 operations, which is much more than the current PoW difficulty.

2. A simpler attack is to first try to find two or more free-start collisions in the coinbase, and then create a merge-mined block.  The collision resistance security of SHA-256 is 128 bits.

The best freestart attacks on SHA-1 requires around 2^60 operations and only produce a single collision (it does not extend to create multiple collisions). There is no known free start collision vulnerability in full SHA-256.

As an example, suppose that a full free start collision that requires 2^100 operations is found. That would be devastating for SHA-256, and everyone (including Bitcoin) will start to move away from SHA-256. However, it still won't affect this particular use.

We can assume the Bitcoin proof-of-work will not have more than 100 zero prefix bits for the next 50 years (assuming Moore's law stays true, and performance per watt keeps increasing exponentially, since currently Bitcoin PoW it has around 72 zero bits). And that would be a very positive scenario, as Bitcoin reward will be 4096 times lower, to keep up with the same amount of mining hashing power the Bitcoin will need to be 4096 times more valuable (1 BTC = 1.3M USD) or each block would need to be 400 GB to pay enough fees.

But the operations involved in finding a collision are not equivalent to PoW hash operations (SHA256D). There will be no pre-built optimized ASICs to execute such attack, and the attack will require the use of GPUs. So we can expect another 1000x performance ratio between them (10 bits).
 
3. Generally attacks start being unpractical and then they get slowly better over time, so when an initial vulnerability is found, there is plenty of time to hard-fork. Assuming the attack only produces a single collision, and a successful and immediate attack is found, the consequence would be a short period of very fast blocks (e.g. 1 per second), followed by a difficulty adjustment that will prevent the merged block-chain from growing without limit. That would give plenty of time for a hard-fork, rendering the attack useless.

4. Even if the attack could find many collisions at once, it would be very easy to prevent the reuse of Bitcoin headers by not allowing the repetition of the Bitcoin header in the last 100 mined blocks. Checking the timestamp of the Bitcoin block, and not allowing the use of an old header (e.g. the header timestamp must be not older than 1 hour, or the median timestamp of the last 10 blocks) can also help.

5. The attack would be immediately detected as the coinbase part presented would surely not be a valid coinbase transaction tail.

So I expect that using the mid-state for coinbase compression in merge-mining will not be a problem for the next 50 years. 
 

We're actually doing this in Rootstock. I had the same thoughts about weakening the security of the hash function, but I don't know any successful freestart attack on SHA-256. This is how we handle it:

Rootstock tag Embedding

The embedding consist of a binary tag including the hash of the Rootstock block header, and it must be unique (there should not be a way to create a Bitcoin block that can be associated with two different Rootstock blocks). There is no accepted standard of where a tag for Merge-mining should be located. It can be located in the coinbase field of the coinbase transaction (the first transaction of a block), in the outputs of the coinbase transaction (generally as an OP_RETURN payload), or in the remaining transactions.

Rootstock standarizes that the tag is located in the coinbase transaction. To specify a Rootstock block hash, the coinbase transaction has to include the RSK tag in any part, generally an input or output script. The RSK tag is: ROOTSTOCK:RskBlockHeaderHash
“ROOTSTOCK:” is the ASCII string consisting of the bytes: 524f4f5453544f434b3a
RskBlockHeaderHash is the  hash of the Rootstock Block header in binary format.
The Rootstock tag is meant to be included following the OP_RETURN OP_PUSHDATA1 opcodes, but this is not mandatory.

The following additional restrictions apply:

The number of bytes after RskBlockHeaderHash to the end of the coinbase transaction must be lower or equal to 128 bytes.
The trail of raw bytes must not contain the binary string "ROOTSTOCK:". 52 4f 4f 54 53 54 4f 43 4b 3a
The probability of the RSK tag to appear by chance is negligible, but pool servers must not rule out the possibility of a rogue Bitcoin address included in an output of the coinbase transaction having this pattern, and being used as an attack to break the validity of the merge-mined header.
The limitation on the number of bytes past the tag generally means that the tag is located within the last 4 outputs of the coinbase transaction.
This restriction allows to create a compressed SPV proof for Rootstock that consist of:
The Bitcoin header (80 bytes)
A Merkle Branch to the Coinbase transaction (approximately 320 bytes)
A mid-state of SHA-256 consuming the head of the coinbase transaction (32 bytes)
A 64 byte aligned chunk containing a trail of the coinbase transaction, including the RSK tag (max. 232 bytes). The trail allows to build a proof that the trail belongs to the coinbase transaction as a free-start hash starting with the given mid-state.
Currently the maximum size of a SPV merge-mining proof is 843 bytes.
 
Also we may extend the tag to 22 bytes to prevent a OP_HASH160 <pubKeyHash> OP_EQUALVERIFY from being a possible Rootstock tag.

A GMaxwell says, I suppose this has already been done.

Do you think it should be better to use a short second transaction to store the tag? It requires more space and it requires having mature UTXOs ready to be consumed for this purpose. That complicates everything.

regards

+1

No block-chain representation will ever be nicer than that DAG-chain.

One more:

5. Bitcoin NG: https://scalingbitcoin.org/montreal2015/presentations/Day1/8-Ittay-eyal-testbed-for-bitcoin-scaling.pdf

But this solution is a trade-off of PoW security against latency: not all blocks are PoW-mined.

One thing is an altcoin: a copy of Bitcoin with minor modifications and nothing interesting. Another thing is a new cryptocurrency design.

This forum has aways been 100% open to discuss any possible cryptocurrency research direction.

Anyway, I'm not planning to implement DagCoin: it's just an idea. But I support all attempts to create new interesting cryptocurrencies. If they work, Bitcoin may use the new technologies using side-chains (and that's why I support side-chains 100%)

Bitcoin benefits from all cryptocurrency research (academic or amateur), because it gives us insight into what are the limits of the technology. As times passes cryptocurrency research is turning more academic, and "new ideas" posted in some blog/forum may become less common.
 

Four possible solutions for a 10 sec blockchain with low wasted PoW:

1. GHOST: https://eprint.iacr.org/2013/881.pdf
2. DECOR+: https://bitslog.wordpress.com/2014/05/07/decor-2/
3. MinCen: https://bitslog.wordpress.com/2014/03/20/mincen-a-new-protocol-to-achieve-instant-payments/
4. DagCoin: https://bitslog.wordpress.com/2015/09/11/dagcoin/

Same as in Bitcoin. Miners are no longer the full nodes maintainers. Only pools and users are.

To incentivize users mining on top of your transaction, you could add a fee to be taken by the confirmating tx. But to prevent orphaning wars, the maximum fee should be limited. DECOR+ is too expensive in terms of additional overhead to implement as per-transaction basis. And if tx fees are shared, txs would need to specify an additional payout address for accumulation of fees. That is not good for a txout-based ledger, because it generates too many spamming utxos. I can work for an account-based ledger. For example, if tx1 attach a fee of F, then the fist confirmation tx gets F*0.4, the next one gets F*0.3, next 0.2, last 0.1.

As I didn't run simulations, I was worried about how would the width vary for different loads on the network. I want users to be able to reference many parent transactions if the braid is getting "thick", and reference only one if the braid is a chain. What would be the rule for the client wallet to decide ? As processing a transaction having many parents has a cost to the network, then this amount must be linked with the transaction PoW somehow.

I read your post and some other posts about this same matter the last months, so I decided to publish my old draft paper, so that others can use those ideas. But I'm not actively working on it.
 

This is true for DagCoin. If a transaction references two parents having conflicting transactions, only one of them becomes valid, and that is the one with more PoW. If both have the same PoW, then the first one is the valid one. Never a transaction validates two conflicting recursively referenced txs.

The only drawback is that which one is the valid one is not immediate obvious: you need the appropriate data structure and the whole transaction tree (up to a checkpoint) to find which one is the valid one.

I think one of the new ideas about DagCoin is that the number of parents you can reference is not chosen by the user, but by the PoW found: the lower the hash, the higher the number of parents you must reference.

It only works if there is a backlog of transactions.

The magic behind any new cryptocurrency token is that since you can create money, you can set an incentive to confirm old transactions. So you can bootstrap your cryptocurrency.

When Bitcoin has no or very low subsidy, it will need a backlog of transactions to go forward. So the problem with DagCoin is bootstrapping. If you have an application where you can keep a flow of transactions going, you can make it work. Also you can add a subsidy to each transaction that has a very high PoW, and create an inflationary cryptocurrency whose price varies with electricity cost and inflates with Moore's law.

More than GHOST, or DECOR+, allowing and merging chain forks seems more like DagCoin (https://bitcointalk.org/index.php?topic=1177633.0)

The idea of DagCoin is that if you merge two double-spends, the one with higher number of confirmations survive. If you merge two competing blocks, then all transactions in one fork will have the same confirmations than on the other fork. So the transaction in the first block referenced must prevail, and the second must be canceled. This make sense when only when you increase the rate of blocks, so an average block interal is below 10 seconds (comparable with propagation time)
 

DagCoin: a cryptocurrency without blocks

Back in 2012 I thought a lot on a new cryptocurrency that could merge the concepts of transaction and block. Each transaction would carry a proof-of-work and reference one or more previous transactions. The resulting authenticated data structure would be a Direct Acyclic Graph (DAG) of transactions where each transaction “confirms” one or more previous transactions. The confirmation security of a transaction would be measured in accumulated amount of proof-of-work referencing (or confirming) the transaction. This structure is well suited for a cryptocurrency without subsidy (such as a side-chain). On the past years I’ve read a couple of similar proposals on bitcointalk (although I cannot find the references now). When the GHOST paper was published, I perceived it as a reinforcement of my idea that a tree could give more security than a chain in case of high rate of transactions.

My open problems…

The problem that I could not solve in 2012 is how to limit the maximum cut of the generated DAG or, in other words, how to prevent all new transactions from referencing the same set of parent transactions. How to create the incentive to “move forward”? The DAG must not increase in “width”, and it should look more like a DAG-chain. Also one must prevent users from choosing old transactions to extend the DAG. I tried several monetary incentive structures to force users to choose newer transactions, but with no result. To know the last “ledger state” there must be a way to consolidate branches. Merging branches should be good, but not too good such that everyone starts merging the same branches over and over. The problem of spam was also less important, as no transaction would be able to get a “free ride” in a block, as each transaction carries PoW. Ultimately the owners of a computer that is being part of a spamming botnet would realize their computers have been hijacked based on the amount of CPU consumed. For instance, if a transaction requires a proof-of-work that takes 1 second in a standard PC, and each transaction is 400 bytes in size, then a botnet consisting in 10K computers may create transaction reaching 3 Mbytes/second. This high network bandwidth usage itself is not a problem, since it can disrupt the network only as long as the attack is active. However, there must be a way to prevent the DAG-chain from growing at that pace. It turns out that the election of an optimal data structure allows the DAG-chain to be compressed, but it requires us to change how we think about double-spends, and how we conceive the “ledger state”.

A Radical Change

The leap of faith required to find an out-of-the-box solution is to think about double-spends not as a boolean attribute, but as a probabilistic attribute, based on comparing the confirmation work on competing transactions. An the security of a transaction, as the confirmation work compared to the the work expected that an adversary may use. Also it requires to forget about the concept of a “global ledger state”. In Bitcoin there is a global ledger state. Chain reorganizations can always rollback the state, but the state is globally consistent. There is a certain probability of the last block rolling back, but the probability is the same for every transaction in that block. In this proposal, the ledger state is just the overlap of all possible transactions, each with its own confirmation probability, and there is no consistent global state.

Design Premise: “The cryptocurrency network benefits from creating a DAG growing as “thin” as possible.”

In other words, having the average maximal cut as low as possible. It seems that referencing many previous transactions (high out degree) can make the DAG thinner only if the following transactions reference the transaction with high out degree, but are themselves of low out degree. So we want high out degree some times, but low out degree another times.

I designed a DAG that tries to fulfill that premise, and an associated incentive structure such that:

 There is a benefit for users to reference as many previous transactions as possible
 Referencing many previous transactions is incentivized only when there are many previous transactions unreferenced.
 There is no competition between users to reference a previous transaction.

Here is the paper draft  –> DagCoin-v4 https://bitslog.files.wordpress.com/2015/09/dagcoin-v41.pdf

This same article can be found in my blog: https://bitslog.wordpress.com/2015/09/11/dagcoin/

It's true that sending to OP_TRUE may be used also as an out-of-band fee channel.
But what would that "significant advantage" be?
It makes a transaction a bit larger, so users must pay more out-of-band fees than the normal case. Also the transaction would not propagate through the network, as it does not have "official" fees.
Also there is no benefit for the client wallet, because those transactions would be understood by a minority of the miners, slowing down confirmation.

So it must be an attack. And only miners having an interface to accept non-standard transactions directly would benefit from the bait. If there is a single miner having such service, then the attack does not work, and only wastes the attacker's money. And it still requires a modified miner software (a miner must prepare his software to enter an orphaning war in case a high OP_TRUE output is found). And the attack can only cause a temporary disruption, until miners do fee delegation (via more OP_TRUEs outputs) or the miner having the majority of the hash rate outperforms the others by a large number of blocks.

I don't see all these conditions for the attack to succeed and be profitable happening anytime soon. 

I'm trying to understand the security of the implementation of 2way peg in Elements, but I find almost no official information on how OP_REORGPROOFVERIFY / OP_WITHDRAWPROOFVERIF should work.

It would be very kind if Blockstream releases some basic documentation to the community, so we can learn how it is supposed to work before reading in the code how it is implemented.

Thanks.
 

Out-of-band fees require coordination between the sender and the miner. It's a private agreement. There is no way to prevent that. Competing miners cannot share out-of-band fees, but out-of-band (private) fees cannot generate contention, so there will be no competition in case a large out-of-band fee appears in a transaction.

There could be the case that the sender sends double-spend transactions to each different miner, using out-of-band fees tailored for each one. This requires that the sender knows a bitcoin address of each miner, and miners are prepared to treat those out-of-band payments as fees, and that miners accept transactions over a communication channel other than the Bitcoin network (which will never forward more than 1 double-spend). So the whole thing looks like an attack more than a real possibility arising from normal usage. In this rare case DECOR+ will fall back to a normal orphaning war. However the subsidy is still shared, and while the subsidy is higher than the rare huge out-of-band fee, no orphaning war will occur.

No. Only in the data structures it uses. GHOST uses uncles to choose the "longest" chain.
DECOR+ uses uncles to split rewards.

These are two complementary concepts.


With DECOR+ you're not "incentivizing" block production on orphaned chains. DECOR+ does not incentivize an orphaned chain to have children. It pays miners that created orphans because of delays in propagation. Incentivize miners to create orphans (uncles) to split a very high (uncommon) block reward. And incentivize miners to prefer one of N competing blocks (all will choose the same parent) in case of a competition (they choose the parent with higher reward).

This is the original post: https://bitslog.wordpress.com/2014/05/02/decor/
And this is a follow up: https://bitslog.wordpress.com/2014/05/07/decor-2/
This is an additional follow up: https://bitslog.wordpress.com/2015/08/16/how-decor-can-eradicate-selfish-mining-incentive-by-design/

This last post about DECOR++ is misleading and actually criticizes DECOR+ without enough good reasons.

DECOR+ eliminates selfish mining by aligning the monetary incentives of miners so that competition is open and not hidden. But it does not eliminate competition.

DECOR++ eliminates selfish mining by design: eliminating competition altogether.  DECOR++ has many other problems, such as not coping well when difficulty changes downward (e.g. back mining may be more profitable than going forward in the short term)

I really prefer DECOR+.