Bitcoin Merkle Tree Flaws and Existent Mitigations for SPV clients

[SergioDemianLerner]

Description

The Bitcoin protocol has a flaw when validating consensus in SPV mode. There is a potential type confusion between Merkle tree middle and leaf nodes. This can lead to two kinds of attacks: leaf transactions that are incorrectly parsed as middle nodes, and middle nodes that are incorrectly parsed as transactions. The vulnerability was made public in 2018 but still it has not been fixed. Correctly implementing SPV wallets require adding additional protections against this protocol flaw. With the proliferation of validating bridges between blockchain, many SPV clients embedded in smart contracts have been deployed, protecting millions of dollars in BTC. However, it seems that very few bridges have protections against the Bitcoin vulnerability. In fact, it was observed that some bridges weaken the verifications on transactions, leading to an expansion of the attack surface.

What is this talk about? Give us as many details as possible.

In this talk we aim to provide the first comprehensive presentation of all the flaws of the Bitcoin Merkle tree design, the vulnerabilities that arise from these flaws, and the potential mitigations, both by changing Bitcoin and by adding specific checks to SPV wallets.

What would an attendee learn from this talk?

The talk is intended for any Bitcoin developer or technical user interested in cybersecurity, but is specially important for developers of Bitcoin SPV clients or Bitcoin bridges using optimistic or SNARK based SPV validation.

Is there anything folks should read up on before they attend this talk?

• The SPV Clients section of the Bitcoin white paper

  Relevant Links

• Disclosure of the vulnerability

• Simplest solution found

• The code that protects the Rootstock bridge against these vulnerabilities

• A paper describing the different flaws

About the Speaker

My name is Sergio Demian Lerner. I'm a bitcoiner, coder, software architect, computer security and cryptocurrency researcher and serial entrepreneur.

I graduated in Computer Science from the University of Buenos Aires and I did my final thesis on peer-to-peer poker. By 2010 I was actively researching anonymous payment systems, in order to combine a p2p currency with my p2p mental poker protocol. In late 2011 I discovered Bitcoin and I began contributing to its design with ideas for improvement.

In 2012 designed a new highly efficient cryptocurrency system, MavePay, based on Guy Fawkes signatures. During 2013 I worked on QixCoin, the first Turing complete cryptocurrency to support my p2p gaming platform. I proposed multiple cryptocurrency protocols such as MAVEPAY (a precursor of Joseph Bonneau’s FawkesCoin), P2PTradeX (the precursor of Blockstream’s sidechains and the second proposed atomic swap method), LIMIO, the Tick method (a precursor of Emin Gün Sirer’s Covenants), the OP_PUSHSIG opcode (a precursor of Segwit), PAMBA, MinCen, MemoHash (a precursor of Dan Boneh’s Ballon Hashing, and the scheme chosen to be a key part in Ethereum’s ETHash design), The Collision POW (a precursor of zCash EquiHash), the “ECDSA” attack (a precursor Patrick McCorry’s of “Smart Contract Bribing Miner” attacks) and BlockPad. I also proposed the first proof system for public file replication, and later applied it in a smart-contract platform to reward full nodes having a copy of the blockchain without TTP (cited by Cecchetti, Fisch & Miers), Also I found the O(N^2) hashing vulnerability on Bitcoin, and later the OP_IF and Rock-and-ROLL efficiency problems, and the first signature malleability attack. I designed the CoVar scheme to improve the blockchain fee market (a precursor of Basu, Easley, O’Hara, and Gün Sirer fee market scheme).

In mid-2013 I designed and prototyped the Firmcoin, a Bitcoin micro-controlled banknote for off-line payments (a precursor of the OpenDime and KongCash), and the DagCoin cryptocurrency (the precursor of Byteball and IOTA coins). To prevent rogue hardware attacks I created the first anti-covert channel ECDSA signature scheme, which was later analyzed and found secure by Pieter Wuille (nowadays a similar technique is used by the Jade hardware wallet). Later I designed the DECOR+ protocol as a proposal to scale Bitcoin to a 5-second block interval. In 2014 I discovered ASICBoost and published a second ASIC optimization technique: using approximate adders. This technique was later rediscovered and published by scientists from the University of Illinois.

In 2013 I discovered a hidden pattern in the blocks mined during the early Bitcoin years, which led to the now widely believed hypothesis that Satoshi owns 1.1M Bitcoins. Since that initial publication, this research has been replicated by other scientists ( 2013, 2013, 2013, 2013, 2014, 2014, 2014, 2019).

In 2015 I designed the RSK Smart Contract platform (a.k.a. Rootstock) and then co-founded RSK Labs, the company that developed and launched the platform. Rootstock included the first cross-chain communication system based on SPV-proofs (cited by SoK paper by Zamyatin et al.). For Roostock, I created more than 100 RSKIPs (RSK Improvement Proposals).

Also I created the first Bitcoin drivechain BIP in order to increase the capabilities of Bitcoin (the currency) using sidechains without increasing Bitcoin block size, and in 2017 I presented an improved BIP. In 2020 I created Syncchains, a new type of sidechain that is protected by design from double-spend attacks to its two-way-peg, and also performs peg-ins and peg-outs in a few confirmation blocks. Additionally I created the Universal Merge Mining Protocol, to enable other blockchains to merge-mine with Bitcoin, the Flyover repayment protocol, to enable faster BTC transfers between Bitcoin and RSK, the Safe Fork-aware Merge-mining Protocol to improve the RSK merge-mining security, the Nakamore consensus system, to improve the decentralization of Bitcoin.

Social Links

Github: @SergioDemianLerner Twitter: @SDLerner Website: bitslog.com

Talk Details

Length of Talk

1 hour.

Preferred Day/Time Slot

Not specified at this time.

[iglesiasbrandon]

hey @SergioDemianLerner thank you for submitting an issue for TABConf 2023! We are reviewing submitted issues and accepting some each week. Keep an eye on this issue in case someone asks questions!

[SergioDemianLerner]

Any news?

[dulcedu]

Woow! It will be amazing to have Sergio Lerner, he is one of the most technical people in Bitcoin, yes he did found RSK but he also was on of the first bitcoin contributors his finding in Bitcoin Core bugs and vulnerabilities. If we can bring Sergio to the Bitcoin community again it will be amazing. His presence in the event and in all the cryptographic talks would be incredible valuable for the high level knowledge he has.

https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/

[iglesiasbrandon]

hey @SergioDemianLerner we have not picked this issue up for the main stage yet but it might get picked up from one of the villages. They will comment on the issue if they have any questions.

[niftynei]

Hey @iglesiasbrandon I'd love to have this on the @base58btc protocol village stage.

Current timeslot is 3.30 - 4.30p on Saturday.

[iglesiasbrandon]

Hey @SergioDemianLerner , We have added a day, time slot, length, and village to this issue. You can find it on the schedule in this view: https://github.com/orgs/TABConf/projects/1/views/9

Please acknowledge by commenting 'ack'.

This will confirm your talk for the Base 58 Protocol Village at TABConf 2023! If we need to make any changes, you will be notified on this issue.

[SergioDemianLerner]

Thank you! I can't confirm now my presence, but I'll confirm in a few days.

[iglesiasbrandon]

sounds good just let us know @SergioDemianLerner

[miketwenty1]

@SergioDemianLerner I hope you can come this is a very interesting topic. Socratic Bitdevs or Base58 Protocol village may want to pick up quick if you can confirm.

[SergioDemianLerner]

Because of the short notice for the confirmation of my talk, I made conflicting arrangements. Is it possible to move my talk to any day before (7th or 8th) so I can leave Atlanta on the 8th night ?

[iglesiasbrandon]

@niftynei ^

[SergioDemianLerner]

?

[SergioDemianLerner]

?

[SergioDemianLerner]

?

[SergioDemianLerner]

?

[SergioDemianLerner]

?

[SergioDemianLerner]

?

[SergioDemianLerner]

I need to buy the plane ticket accordingly. Any news?

[iglesiasbrandon]

hey @SergioDemianLerner we need to wait on @niftynei to add a comment because this is her village. I will ping her about this now.

[niftynei]

hi apologies for the delay, i was traveling last week.

There's a 9a-10a slot available on the schedule on day 3

[SergioDemianLerner]

Thank you. For me, anything on day 3 is much better.

[SergioDemianLerner]

Is it confirmed on day 3 then ?

[iglesiasbrandon]

ill go ahead and move it to that slot ( Day 3 from 9 AM to 10 AM ET. @SergioDemianLerner @niftynei

[niftynei]

Is it confirmed on day 3 then ?

Yes!

[iglesiasbrandon]

Hey @SergioDemianLerner, I am closing this issue since it's completed. Thank you for all of the effort you put into it!