[Bitcoin-development] About Compact SPV proofs via block header commitments

[Bitcoin-development] About Compact SPV proofs via block header commitments

[Sergio Lerner]

I read the post in this threads about Compact SPV proofs via block
header commitments (archived e-mail in
https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg04318.html).
I was working on the same problem almost at the same time, which is
something that's becoming very common nowadays..

The proposal starts with the following claim:

"In simple payment verification (SPV) proofs it is currently necessary
that every intervening block header be provided between two blocks in
order to establish both connectivity and proof of work."

I think this is false. Let's first assume that at the time of an attack
we're connected only to the attacker (no honest nodes). An
non-interactive SPV proof needs to prove that a transaction belongs to
the best chain because creating a counterfeit proof cost more than the
amount of money involved in the proof. Suppose that the proof consist at
least of a block header and a merkle branch to the claimed transaction.

Do the proof need connectivity with the last checkpoint known by the
verifier? (here checkpoint is any block known for sure to be in the best
chain)

Not much, because connectivity only proves that the proof was not
pre-computed before the checkpoint. Only if the checkpoint is very near
(say 10 blocks back) it brings some practical evidence that the attacker
did not have much time to prepare an attack.
 
Do the proof need to know the interleaving proof-of-work?

Not much. If the distance between blocks is less than 2016 blocks, then
the difficulty may have change only by a factor of 4. Currently
difficult adjustments are much lower (I suppose that about 1.1 or so).
Then one can assume that the proof block target difficulty is almost the
same as the last known difficulty if the block distance is less than
2016. If the distance is more, we just load all the interleaving
re-target blocks to detect the actual difficulty.

Do the proof need to have a certain number of  confirmations?

Yes and no, because this is the only evidence that the prover has either
spend money in creating the fake block or took a genuine block.
The cost of creating a fake block can be approximated as the minimum of:
- The current reward of the block (since currently fees are much lower
than the reward)
- The average block fees (when the reward goes to zero)
- The minimum electricity cost of mining the block.

As time passes one could assume that the electricity cost of mining will
approach the other two. 

But there is the problem of parallel synchronized attacks: if an
attacker can reuse the same fake SPV proof to attack several victims,
then the reward for cheating increases proportionally but the cost stays
the same.
For instance, if 6 confirmations are required, and each block can hold
2000 transactions, the attacker can find 2000 victims and re-use the
same 6 block chain to "prove" payments to 2000 victims. Also the cost of
mining 6 blocks can be amortized by mining 7, and attacking in the first
two 4000 victims, etc...

Any scheme than relies on non-interactive SPV proofs will fail if
Bitcoin will scale up-to a point where victims can be easily found and
synchronized.
So I think one should assume that at least one peer is honest...

But if we assume than during the attack least one peer is honest, then
we could directly ask every peer to give us the blocks of their
best-chains at the same heights of the presented proof.  No back-links
are necessary.  If any peer shows a different block, then we should
carefully detect which of the two nodes is the one attacking us and ban
it, by downloading the best-chain headers from the last checkpoint to
the block of the proof.  This would be rare so I don't see when the
back-links can help.

The use case should be:

==Use cases==

For SPV client that has just come online asks peers what is the last block height/time. 
If a peer replies with an old block, then that peer is still downloading the block-chain and it's ignored.
For the remaining peers, the client starts asking for parents blocks until all parents agree (this is the last common parent). 
If (U)TxO hash-tree commitments are available, then the wallet is updated using this data from the common parent block. 

At the same time the client retrieves compact non-interactive proofs-of-inclusion (possibly orphan) for its transactions 
without having to download every intervening block header.

Is there something wrong with this?
 
Best regards,
Sergio.

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Mark Friedenbach]

Sergio,

First of all, let's define what an SPV proof is: it is a succinct
sequence of bits which can be transmitted as part of a non-interactive
protocol that convincingly establishes for a client without access to
the block chain that for some block B, B has an ancestor A at some
specified height and work distance back, and the cost of creating a
false proof is at least as much work as it claims to represent.

The previous email you quote demonstrates how with additional backlink
commitments this can be done in logarithmic space: using an average of
log(N) headers to construct an SPV proof from block A to block B where N
is the height differential. It can be verified without access to the
block chain or other peers. Note that with back links the cost of
creating a fraudulent SPV proof is the same as 51% attacking bitcoin
itself. The protocol you outlined does not have this property.

Other than that, honestly I'm not really sure what you are trying to
accomplish. An interactive proof is does not meet the above requirements
and is not usable for the driving application of two-way pegs. Maybe you
had some other application in mind? I've looked at your SmartSPV
proposal, but fail to see how it doesn't reduce to simply blind trust in
your view of the network from your peers. SPV proofs on the other hand
put an economic cost to fraud.

On 04/26/2014 06:08 PM, Sergio Lerner wrote:
> I read the post in this threads about Compact SPV proofs via block
> header commitments (archived e-mail in
> https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg04318.html).
> I was working on the same problem almost at the same time, which is
> something that's becoming very common nowadays..
> 
> The proposal starts with the following claim:
> 
> "In simple payment verification (SPV) proofs it is currently necessary
> that every intervening block header be provided between two blocks in
> order to establish both connectivity and proof of work."
> 
> I think this is false. Let's first assume that at the time of an attack
> we're connected only to the attacker (no honest nodes). An
> non-interactive SPV proof needs to prove that a transaction belongs to
> the best chain because creating a counterfeit proof cost more than the
> amount of money involved in the proof. Suppose that the proof consist at
> least of a block header and a merkle branch to the claimed transaction.
> 
> Do the proof need connectivity with the last checkpoint known by the
> verifier? (here checkpoint is any block known for sure to be in the best
> chain)
> 
> Not much, because connectivity only proves that the proof was not
> pre-computed before the checkpoint. Only if the checkpoint is very near
> (say 10 blocks back) it brings some practical evidence that the attacker
> did not have much time to prepare an attack.
>  
> Do the proof need to know the interleaving proof-of-work?
> 
> Not much. If the distance between blocks is less than 2016 blocks, then
> the difficulty may have change only by a factor of 4. Currently
> difficult adjustments are much lower (I suppose that about 1.1 or so).
> Then one can assume that the proof block target difficulty is almost the
> same as the last known difficulty if the block distance is less than
> 2016. If the distance is more, we just load all the interleaving
> re-target blocks to detect the actual difficulty.
> 
> Do the proof need to have a certain number of  confirmations?
> 
> Yes and no, because this is the only evidence that the prover has either
> spend money in creating the fake block or took a genuine block.
> The cost of creating a fake block can be approximated as the minimum of:
> - The current reward of the block (since currently fees are much lower
> than the reward)
> - The average block fees (when the reward goes to zero)
> - The minimum electricity cost of mining the block.
> 
> As time passes one could assume that the electricity cost of mining will
> approach the other two. 
> 
> But there is the problem of parallel synchronized attacks: if an
> attacker can reuse the same fake SPV proof to attack several victims,
> then the reward for cheating increases proportionally but the cost stays
> the same.
> For instance, if 6 confirmations are required, and each block can hold
> 2000 transactions, the attacker can find 2000 victims and re-use the
> same 6 block chain to "prove" payments to 2000 victims. Also the cost of
> mining 6 blocks can be amortized by mining 7, and attacking in the first
> two 4000 victims, etc...
> 
> Any scheme than relies on non-interactive SPV proofs will fail if
> Bitcoin will scale up-to a point where victims can be easily found and
> synchronized.
> So I think one should assume that at least one peer is honest...
> 
> But if we assume than during the attack least one peer is honest, then
> we could directly ask every peer to give us the blocks of their
> best-chains at the same heights of the presented proof.  No back-links
> are necessary.  If any peer shows a different block, then we should
> carefully detect which of the two nodes is the one attacking us and ban
> it, by downloading the best-chain headers from the last checkpoint to
> the block of the proof.  This would be rare so I don't see when the
> back-links can help.
> 
> The use case should be:
> 
> ==Use cases==
> 
> For SPV client that has just come online asks peers what is the last block height/time. 
> If a peer replies with an old block, then that peer is still downloading the block-chain and it's ignored.
> For the remaining peers, the client starts asking for parents blocks until all parents agree (this is the last common parent). 
> If (U)TxO hash-tree commitments are available, then the wallet is updated using this data from the common parent block. 
> 
> At the same time the client retrieves compact non-interactive proofs-of-inclusion (possibly orphan) for its transactions 
> without having to download every intervening block header.
> 
> Is there something wrong with this?
>  
> Best regards,
> Sergio.
> 
> ------------------------------------------------------------------------------
> Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software
> Java Based Open Source Intranet - Social, Extensible, Cloud Ready
> Get Started Now And Turn Your Intranet Into A Collaboration Platform
> http://p.sf.net/sfu/ExoPlatform
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Sergio Lerner]

El 26/04/2014 10:43 p.m., Mark Friedenbach escribió:
> Sergio,
>
> First of all, let's define what an SPV proof is: it is a succinct
> sequence of bits which can be transmitted as part of a non-interactive
> protocol that convincingly establishes for a client without access to
> the block chain that for some block B, B has an ancestor A at some
> specified height and work distance back, and the cost of creating a
> false proof is at least as much work as it claims to represent.
Ok. I was thinking with another definition SPV proof.

For me a SPV proof is a sequence of bits which can be transmitted as
part of a non-interactive protocol that convincingly establishes for a
client without access to the block chain that a block B is part of the
best-chain.

I understand that SPV nodes require SPV proofs as defined in my
definition, but I can't realize how to prove that SPV nodes require SPV
proofs under your definition. So your definition sounds to me like one
possible solution, but not the need.
 
Is your definition something well-established in the community?

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Mark Friedenbach]

I don't think there's an official definition of "SPV proof." I wasn't
trying to make a argument "from definition" (that would be fallacious!).
Rather I suspected that we had different concepts in mind and wanted to
check.

That said, I do think that the definition I gave matches how the term is
used in the Satoshi whitepaper, and the way in which SPV clients like
BitcoinJ work. "Best chain" is typically taken to mean the most-work,
*valid* chain. Without invoking moon math or assumptions of honest peers
and jamming-free networks, the only way to know a chain is valid is to
witness the each and every block. SPV nodes on the other hand, simply
trust that the most-work chain is a valid chain, based on economic
arguments about the opportunity cost of mining invalid blocks. These SPV
nodes use block headers as proofs to determine the most-work block
connected to the genesis block or most recent checkpoint. So yes,
operationally at least this is what the community seems to mean by "SPV
proof".

Now regarding your use case:

> For the remaining peers, the client starts asking for parents blocks 
> until all parents agree (this is the last common parent).

This linear scan of block headers is what I would prefer to avoid. By
using back-links you make it have log(N) space usage.

On 04/26/2014 07:39 PM, Sergio Lerner wrote:
> El 26/04/2014 10:43 p.m., Mark Friedenbach escribió:
>> Sergio,
>> 
>> First of all, let's define what an SPV proof is: it is a succinct 
>> sequence of bits which can be transmitted as part of a 
>> non-interactive protocol that convincingly establishes for a
>> client without access to the block chain that for some block B, B
>> has an ancestor A at some specified height and work distance back,
>> and the cost of creating a false proof is at least as much work as
>> it claims to represent.
> Ok. I was thinking with another definition SPV proof.
> 
> For me a SPV proof is a sequence of bits which can be transmitted as
>  part of a non-interactive protocol that convincingly establishes
> for a client without access to the block chain that a block B is part
> of the best-chain.
> 
> I understand that SPV nodes require SPV proofs as defined in my 
> definition, but I can't realize how to prove that SPV nodes require 
> SPV proofs under your definition. So your definition sounds to me 
> like one possible solution, but not the need.
> 
> Is your definition something well-established in the community?
> 
> 
> 
> 
> ------------------------------------------------------------------------------
>
>
> 
Start Your Social Network Today - Download eXo Platform
> Build your Enterprise Intranet with eXo Platform Software Java Based 
> Open Source Intranet - Social, Extensible, Cloud Ready Get Started 
> Now And Turn Your Intranet Into A Collaboration Platform 
> http://p.sf.net/sfu/ExoPlatform 
> _______________________________________________ Bitcoin-development 
> mailing list Bitcoin-development@lists.sourceforge.net 
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Sergio Lerner]

El 27/04/2014 03:43 a.m., Mark Friedenbach escribió:
> I don't think there's an official definition of "SPV proof." I wasn't
> trying to make a argument "from definition" (that would be fallacious!).
> Rather I suspected that we had different concepts in mind and wanted to
> check.
So to disambiguate I define the most general definition as a NPP
(non-interactive payment proof).
> Without invoking moon math or assumptions of honest peers
> and jamming-free networks, the only way to know a chain is valid is to
> witness the each and every block. SPV nodes on the other hand, simply
> trust that the most-work chain is a valid chain, based on economic
> arguments about the opportunity cost of mining invalid blocks. 
I argue that you cannot talk about "the most-work chain" without
actually making an assumption about honest peers.
If you do not make the assumption, you compute the "economic arguments"
wrong.
> Now regarding your use case:
>
>> For the remaining peers, the client starts asking for parents blocks 
>> until all parents agree (this is the last common parent).
> This linear scan of block headers is what I would prefer to avoid. By
> using back-links you make it have log(N) space usage.
First this is a method that uses NPPs, not SPV proofs.
Since the method chooses all peers that are synchronized (have the
latest current block) then going back means only skipping a potential
short fork (which I suppose has never been more than 3 blocks during
normal network conditions). You're looking for a common ancestor, not
the checkpoint.
So the linear scan is actually O(1).
The exact value can be approximated by the sum of the convergent
infinite geometrical sequence of forking probabilities, which it's about
1.03 without considering selfish-mining, and probably less than 2.03
considering it.

 

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Mark Friedenbach]

On 04/27/2014 05:36 AM, Sergio Lerner wrote:
>> Without invoking moon math or assumptions of honest peers and
>> jamming-free networks, the only way to know a chain is valid is to 
>> witness the each and every block. SPV nodes on the other hand,
>> simply trust that the most-work chain is a valid chain, based on
>> economic arguments about the opportunity cost of mining invalid
>> blocks.
> I argue that you cannot talk about "the most-work chain" without 
> actually making an assumption about honest peers.

I should have said "without invoking moon math or interactive protocols
requiring honest peers over jamming-free networks." The interactive
protocol was more the point than the honest peers and jamming-free
network. Yes, without an honest peer and an un-jammed network, you might
never learn about the most-work chain in the first place. But having the
security of the proof not depend on query access to an honest full node
is absolutely necessary for some applications and certainly desirable in
others.

Although strictly speaking what I said may not be 100% true. The single
alternative solution I've seen involves some sort of Fiat–Shamir
transform that could give you a probabilistic proof by including random
additional paths through the block chain chosen based on the combined
hash of the headers. However this is disadvantageous as it massively
increases the proof size and verification time, and you have to include
a lot of data to achieve assurance that more work was required to
generate the fraud than an honest chain.

> If you do not make the assumption, you compute the "economic
> arguments" wrong.

Not necessarily. By requiring connectivity you know that what you are
receiving is built off of the main chain, for example, and you can still
make assumptions about resulting opportunity costs.

> First this is a method that uses NPPs, not SPV proofs. Since the
> method chooses all peers that are synchronized (have the latest
> current block) then going back means only skipping a potential short
> fork (which I suppose has never been more than 3 blocks during normal
> network conditions). You're looking for a common ancestor, not the
> checkpoint. So the linear scan is actually O(1). The exact value can
> be approximated by the sum of the convergent infinite geometrical
> sequence of forking probabilities, which it's about 1.03 without
> considering selfish-mining, and probably less than 2.03 considering
> it.

Unless you're connected to attacker nodes which are wildly divergent
from each other. It's relatively easy to create a massive fake history
of difficulty-1 blocks.

If you assume honest peers things get very easy. But that's not a safe
assumption to be making. With back-link block-history commitments, on
the other hand, an interactive protocol allows you to do a binary search
to find common ancestors, and have trust that the intermediate links
actually exist.

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Sergio Lerner]

[-- Attachment #1: Type: text/plain, Size: 4739 bytes --]


On 27/04/2014 02:05 p.m., Mark Friedenbach wrote:
>
> On 04/27/2014 05:36 AM, Sergio Lerner wrote:
>>> Without invoking moon math or assumptions of honest peers and
>>> jamming-free networks, the only way to know a chain is valid is to 
>>> witness the each and every block. SPV nodes on the other hand,
>>> simply trust that the most-work chain is a valid chain, based on
>>> economic arguments about the opportunity cost of mining invalid
>>> blocks.
>> I argue that you cannot talk about "the most-work chain" without 
>> actually making an assumption about honest peers.
> I should have said "without invoking moon math or interactive protocols
> requiring honest peers over jamming-free networks." The interactive
> protocol was more the point than the honest peers and jamming-free
> network. Yes, without an honest peer and an un-jammed network, you might
> never learn about the most-work chain in the first place. But having the
> security of the proof not depend on query access to an honest full node
> is absolutely necessary for some applications and certainly desirable in
> others.
The problem is not having or not access to a honest full node. The SPV
client MUST have access to a honest full node sometime.
The problem is WHEN. One can make the security assumption that during an
attack (someone gives you a fake block) you also loose the possibility
to reach any honest node. Then SPV proofs come into play.

Here are the security assumptions I added to my post about SmartSPV to
clarify this:

*Security Assumptions
*

First let’s review the main security assumption of headers-only SPV:

  * The attacker does not control all your communications with the
    payment network.

This means that there is at least a single connected peer that behaves
honestly. This assumption is quite strong and may not hold during short
periods of time, such as during application power-on (when only a few
peers have been connected), or when moving to a place where the ISP is
untrusted. For SmartSPV we’ll require weaker security assumptions:

  * The attacker cannot control all your communications with the payment
    network for more than a fixed period of time (e.g. 2016 blocks for
    Bitcoin or approximately 15 days)
  * The attacker is rational: it won’t spend an huge amount of money to
    steal a much smaller amount.

This assumptions imply that the attacker may control all your Internet
connections while he sends you a malicious block branch containing a
fake payment to you.


>
>> First this is a method that uses NPPs, not SPV proofs. Since the
>> method chooses all peers that are synchronized (have the latest
>> current block) then going back means only skipping a potential short
>> fork (which I suppose has never been more than 3 blocks during normal
>> network conditions). You're looking for a common ancestor, not the
>> checkpoint. So the linear scan is actually O(1). The exact value can
>> be approximated by the sum of the convergent infinite geometrical
>> sequence of forking probabilities, which it's about 1.03 without
>> considering selfish-mining, and probably less than 2.03 considering
>> it.
> Unless you're connected to attacker nodes which are wildly divergent
> from each other. It's relatively easy to create a massive fake history
> of difficulty-1 blocks.
Since in my use case (SmartSPV) I proposed you start from the most
recent block and go backwards, the attacker must compete in PoW with the
real current difficulty informed.
Suppose the SPV client looks for 6-block chains backwards starting from
the last current block. Suppose you know or estimate the current network
difficulty. Suppose a malicious peer creates a fake 6-block chain Cm and
the honest peer gives you the 6-block chain Ch. If Ch has not the
expected work it's discarded. If both has the expected work, then you
better not true any of them and walk their parents until you find a
common parent. That's the block you should trust. If you don't have an
honest node connected, then the only decide to trust or not Cm is by
it's accumulated work (and you have already a bound for it)


> If you assume honest peers things get very easy. But that's not a safe
> assumption to be making. With back-link block-history commitments, on
> the other hand, an interactive protocol allows you to do a binary search
> to find common ancestors, and have trust that the intermediate links
> actually exist.
So you agree that:  you need a periodic connection to a honest node, but
during an attack you may loose that connection. This is the assumption
we should be working on, and my use case (described in
http://bitslog.wordpress.com/2014/04/25/smartspv-a-better-simplified-payment-verification-for-smartphones/)
assumes that.


[-- Attachment #2: Type: text/html, Size: 6033 bytes --]

Re: [Bitcoin-development] About Compact SPV proofs via block header commitments

[Mark Friedenbach]

On 04/28/2014 07:32 AM, Sergio Lerner wrote:
> So you agree that:  you need a periodic connection to a honest node, but
> during an attack you may loose that connection. This is the assumption
> we should be working on, and my use case (described in
> http://bitslog.wordpress.com/2014/04/25/smartspv-a-better-simplified-payment-verification-for-smartphones/)
> assumes that.

No, that's sortof tangential. What you are solving is some higher level
application on top of SPV proofs, compact or otherwise. SPV proofs have
many broad applications, such as 2-way pegs where proof-of-work is used
to reach consensus over the most-work side-chain header, and a non-51%
attack is detectable from observed difficulty and interblock times. Do
you need an honest peer to learn about the best chain? Yes. Do you need
to *trust* that you have an honest peer? No, because a non-51% attack
against you is probabilistically detectable with existing tools.

Maybe SmartSPV is useful, maybe not. The application domain is not
something I've been concerned with in the past. But what you describe is
a higher-level protocol that uses block headers to determine which chain
to trust. My simple point from the start has been that you can use
back-link commitments and compact SPV proofs to accomplish what you want
fewer messages, less bandwidth, and equal security. The two proposals
are not in conflict with each other.