Re: [Bitcoin-development] Version bits proposal

[Sergio Lerner]

I like the idea but I think we should leave at least 16 bits of the
version fixed as an extra-nonce.
If we don't then miners may use them as a nonce anyway, and mess with
the soft-fork voting system.
My original proposal was this: https://github.com/bitcoin/bitcoin/pull/5102

Best regards


--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Reducing the block rate instead of increasing the maximum block size

[Sergio Lerner]

On 11/05/2015 04:25 p.m., Leo Wandersleb wrote:
> I assume that 1 minute block target will not get any substantial support but
> just in case only few people speaking up might be taken as careful
support of
> the idea, here's my two cents:
>
> In mining, stale shares depend on delay between pool/network and the
miner. This
> varies substantially globally and as Peter Todd/Luke-Jr mentioned,
speed of
> light will always keep those at a disadvantage that are 100 light
milli seconds
> away from the creation of the last block. If anything, this warrants
to increase
> block target, not reduce. (The increase might wait until we have
miners on Mars
> though ;) )

An additional delay of 200 milliseconds means loosing approximately 0.3%
of the revenue.
Do you really think this is going to be the key factor to prevent a
mining pool from being used?
There are lot of other factors, such as DoS protections, security,
privacy, variance, trust, algorithm to distribute shares, that are much
more important than that.

And having a 1 minute block actually reduces the payout variance 10x, so
miners will be happy for that. And many pool miners may opt to do solo
mining, and create new full-nodes.

>
>
> If SPV also becomes 10 times more traffic intensive, I can only urge
you to
> travel to anything but central Europe or the USA.
The SPV traffic is minuscule. Bloom-filers are an ugly solution that
increases bandwidth and does not provide a real privacy solution.
Small improvements in the wire protocol can reduce the traffic two-fold.

>
>
> I want bitcoin to be the currency for the other x billion and thus I
oppose any
> change that moves the balance towards the economically upper billion.
Because having a 10 minute rate Bitcoin is a good Internet money. If you
have a 1 minute rate, then it can also be a retail payment method, an
virtual game trading payment method, a gambling, XXX-video renting 
(hey, it takes less than 10 minutes to see one of those :), and much more.

You can reach more billions by having near instant payments.
Don't tell me about the morning caffe, I would like that everyone is
buying their coffe with Bitcoin and there are millions of users before
we figure out how to do that off-chain.

Best regards,
 Sergio.


--
One dashboard for servers and applications across Physical-Virtual-Cloud 
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] Reducing the block rate instead of increasing the maximum block size

[Sergio Lerner]

In this e-mail I'll do my best to argue than if you accept that
increasing the transactions/second is a good direction to go, then
increasing the maximum block size is not the best way to do it. I argue
that the right direction to go is to decrease the block rate to 1
minute, while keeping the block size limit to 1 Megabyte (or increasing
it from a lower value such as 100 Kbyte and then have a step function).
I'm backing up my claims with many hours of research simulating the
Bitcoin network under different conditions [1].  I'll try to convince
you by responding to each of the arguments I've heard against it.

Arguments against reducing the block interval

1. It will encourage centralization, because participants of mining
pools will loose more money because of excessive initial block template
latency, which leads to higher stale shares

When a new block is solved, that information needs to propagate
throughout the Bitcoin network up to the mining pool operator nodes,
then a new block header candidate is created, and this header must be
propagated to all the mining pool users, ether by a push or a pull
model. Generally the mining server pushes new work units to the
individual miners. If done other way around, the server would need to
handle a high load of continuous work requests that would be difficult
to distinguish from a DDoS attack. So if the server pushes new block
header candidates to clients, then the problem boils down to increasing
bandwidth of the servers to achieve a tenfold increase in work
distribution. Or distributing the servers geographically to achieve a
lower latency. Propagating blocks does not require additional CPU
resources, so mining pools administrators would need to increase
moderately their investment in the server infrastructure to achieve
lower latency and higher bandwidth, but I guess the investment would be low.

2. It will increase the probability of a block-chain split

The convergence of the network relies on the diminishing probability of
two honest miners creating simultaneous competing blocks chains. To
increase the competition chain, competing blocks must be generated in
almost simultaneously (in the same time window approximately bounded by
the network average block propagation delay). The probability of a block
competition decreases exponentially with the number of blocks. In fact,
the probability of a sustained competition on ten 1-minute blocks is one
million times lower than the probability of a competition of one
10-minute block. So even if the competition probability of six 1-minute
blocks is higher than of six ten-minute blocks, this does not imply
reducing the block rate increases this chance, but on the contrary, 
reduces it.

3, It will reduce the security of the network

The security of the network is based on two facts:
A- The miners are incentivized to extend the best chain
B- The probability of a reversal based on a long block competition
decreases as more confirmation blocks are appended.
C- Renting or buying hardware to perform a 51% attack is costly.

A still holds. B holds for the same amount of confirmation blocks, so 6
confirmation blocks in a 10-minute block-chain is approximately
equivalent to 6 confirmation blocks in a 1-minute block-chain.
Only C changes, as renting the hashing power for 6 minutes is ten times
less expensive as renting it for 1 hour. However, there is no shop where
one can find 51% of the hashing power to rent right now, nor probably
will ever be if Bitcoin succeeds. Last, you can still have a 1 hour
confirmation (60 1-minute blocks) if you wish for high-valued payments,
so the security decreases only if participant wish to decrease it.

4. Reducing the block propagation time on the average case is good, but
what happen in the worse case?

Most methods proposed to reduce the block propagation delay do it only
on the average case. Any kind of block compression relies on both
parties sharing some previous information. In the worse case it's true
that a miner can create and try to broadcast a block that takes too much
time to verify or bandwidth to transmit. This is currently true on the
Bitcoin network. Nevertheless there is no such incentive for miners,
since they will be shooting on their own foots. Peter Todd has argued
that the best strategy for miners is actually to reach 51% of the
network, but not more. In other words, to exclude the slowest 49%
percent. But this strategy of creating bloated blocks is too risky in
practice, and surely doomed to fail, as network conditions dynamically 
change. Also it would be perceived as an attack to the network, and the
miner (if it is a public mining pool) would be probably blacklisted.

5. Thousands of SPV wallets running in mobile devices would need to be
upgraded (thanks Mike).

That depends on the current upgrade rate for SPV wallets like Bitcoin
Wallet  and BreadWallet. Suppose that the upgrade rate is 80%/year: we
develop the source code for the change now and apply the change in 

Re: [Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Sergio Lerner]

El 10/05/2015 06:07 p.m., Gregory Maxwell escribió:
> On Sun, May 10, 2015 at 8:45 PM, Sergio Lerner
>  wrote:
>> Can the system by gamed?
> Users can pay fees or a portion of fees out of band to miner(s); this
> is undetectable to the network.
Then this is exactly what is needed. Let me explain.

I know of 5 methods for a user to pay fees to a miner. I will explain
each method and why these methods do not prevent the fee market from
being created:

1) By transaction fees

This is the standard, which would be limited by the CoVar algorithm, and
would create the fee market, if it were the only way to pay fees.

2) By creating multiple transactions, each adding an output that pays to
each miner (to a known miner address) the fees. User does not
pre-negotiate anything with miners.

This requires a transaction to have an additional output and requires
sending through the p2p network one different transaction to each miner,
each having an output with a "known" address of that miner. But the
network does not propagates double-spends, so those transaction would
need to be sent directly to the top miners, and to all at the same time.
The IP addresses of the top miners are not generally publicly available,
and then may not accept new incoming connections. Also having an
additional output means the transactions would be larger, so they will
score lower by any metric the miner uses to choose transactions. Last,
miners must be programmed to automatically interpret payments to their
addresses as fees. The resulting protocol is very difficult to do
reliably, expensive, as any delay would make one miner receive the
transaction from other miner and reject the double-spend that is being
send directly to it, increasing the average confirmation time.

3) By adding an anyone-can-spend output for fees, so the miner can spend
that output in the same block.  User does not pre-negotiate anything
with miners.

We can hard-fork not to allow spending outputs created in the same
block. This is a drawback, unless we reduce the block rate, which is my
proposal. However, spending in the same block also requires an storing
in the block an additional input, which consumes at least 40 bytes more,
and the transaction containing the input cannot be relayed to the
network in advance. Then the block that uses this method to collect fees
from many transactions will propagate slower, and the miner may end
loosing money. The any-one-can-spend output would take approximately 10
bytes. So if transmitting 10+40=50 bytes, cost more than the fees
earned, then miners do not have an incentive to game the system. It's
has been studied that "each kilobyte costs an additional 80ms delay
until a majority knows about the block." (Information propagation in the
Bitcoin network). So 50 bytes costs 3.9 ms in propagation time, which
having a a 25 BTC subsidy is roughly equivalent to 0.2 mBTC. Currently
this is more than what transactions do pay in fees (about 0.1 mBTC), so
this should not be a problem for at least 5 years. And again, we could
just prevent spending outputs in the same block they are created.

4) Using a transaction having a single input having exactly the desired
output amount plus fees and signing the input with SIGHASH_SINGLE |
SIGHASH_ANYONECANPAY and adding to the transaction a single output with
the desired amount. The miner will be able to join many of these
transactions and finally add an output to collect all fees together,
without using standard transaction fees.

This is unreliable and cannot be systematically repeated without
creating a pre-transaction just to prepare the single input having the
amount plus fees exactly. The pre-transaction would need to pay fees, so
the problem is not avoided, just moved around.

5) By negotiating out of band with the miner previously. Anything could
be agreed by the user and the miner.

This actually creates a parallel out-of-band market for fees, which is
exactly what we want. If a user-to-miner pre-negotiation will take
place, then the miner can establish whatever price policy he wants to
compete and stay in business, as block data propagation costs money. So
there will be two fee markets, the "out-of-band" market, and the
"in-band" market, and both should converge.

My conclusion is that fee markets will be created, and any alternate
fee-paying methods (without a pre-negotiation) are not reliable nor
cost-saving options. The full proposal would be to use the CoVar method,
reduce the block rate to 1 minute, and do not allow spending outputs in
the same block they are created.

Best regards,
 Sergio.



--
One dashboard for servers and applications across Physical-Virtual-Cloud 
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transacti

[Bitcoin-development] A way to create a fee market even without a block size limit (2013)

[Sergio Lerner]

Two years ago I presented a new way to create a fee market that does not
depend on the block chain limit.

This proposal has not been formally analyzed in any paper since then,
but I think it holds a good promise to untangle the current problem
regarding increasing the tps and creating the fee market. BTW, think the
maximum tps should be increased, but not by increasing the block size,
but by increasing the block rate (I'll expose why in my next e-mail).

The original post is here (I was overly optimistic back then):
https://bitcointalk.org/index.php?topic=147124.msg1561612#msg1561612

I'll summarize it here again, with a little editing and a few more
questions at the end:

The idea is simple, but requires a hardfork, but is has minimum impact
in the code and in the economics.

Solution: Require that the set of fees collected in a block has a
dispersion below a threshold. Use, for example, the Coefficient of
Variation (http://en.wikipedia.org/wiki/Coefficient_of_variation). If
the CoVar is higher than a fixed threshold, the block is considered invalid.

The Coefficient of variation is computed as the standard deviation over
the mean value, so it's very easy to compute. (if the mean is zero, we
assume CoVar=0). Note that the CoVar function *does not depend on the
scale*, so is just what a coin with a floating price requires.

This means that if there are many transactions containing high fees in a
block, then free transactions cannot be included.
The core devs should tweak the transaction selection algorithm to take
into account this maximum bound.

*Example*

If the transaction fee set is: 0,0,0,0,5,5,6,7,8,7
The CoVar is 0.85
Suppose we limit the CoVar to a maximum of 1.

Suppose the transaction fee set is: 0,0,0,0,0,0,0,0,0,10
Then the CoVar is 3.0

In this case the miner should have to either drop the "10" from the fee
set or drop the zeros. Obviously the miner will drop some zeros, and
choose the set: 0,10, that has a CoVar of 1.

*Why it reduces the Tx spamming Problem?*

Using this little modification, spamming users would require to use
higher fees, only if the remaining users in the community rises their
fees. And miners won't be able to include an enormous amounts of
spamming txs.

*Why it helps solving **the tragedy-of-the-commons fee "problem"?*

As miners are forced to keep the CoVar below the threshold, if people
rises the fees to confirm faster than spamming txs, automatically
smamming txs become less likely to appear in blocks, and fee-estimators
will automatically increase future fees, creating a the desired feedback
loop.

*Why it helps solving the block size problem?*

Because if we increase the block size, miners that do not care about the
fee market won't be able to fill the block with spamming txs and destroy
the market that is being created. This is not a solution against an
attacker-miner, which can always fill the block with transactions.

*Can the system by gamed? Can it be attacked?*

I don't think so. An attacker would need to spend a high amount in fees
to prevent transactions with low fees to be included in a block.
However, a formal analysis would be required. Miller, Gun Sirer, Eyal..
Want to give it a try?
*
Can create a positive feedback to a rise the fees to the top or push
fess to the bottom?

*Again, I don't think so. This depends on the dynamics between the each
node's fee estimator and the transaction backlog. MIT guys?

*Doesn't it force miners to run more complex algorithms (such as linear
programming) to find the optimum tx subset ?

*Yes, but I don't see it as a drawback, but as a positive stimulus for
researchers to develop better tx selection algorithms. Anyway, the
greedy algorithm of picking the transactions with highest fees fees
would be good enough.

*
PLEASE don't confuse the acronym CoVar I used here with co-variance.*

Best regard,
  Sergio.



--
One dashboard for servers and applications across Physical-Virtual-Cloud 
Widest out-of-the-box monitoring support with 50+ applications
Performance metrics, stats and reports that give you Actionable Insights
Deep dive visibility with transaction tracing using APM Insight.
http://ad.doubleclick.net/ddm/clk/290420510;117567292;y___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] "network disruption as a service" and proof of local storage

[Sergio Lerner]

Matt is right:  the goal is to prove digital copies of a public file.
Nothing more, nothing less.

Regarding the IP, I don't claim that every machine should provide the
protocol. Mobiles phones shouldn't. But machines that what to be
prioritized in some way or that want to be rewarded for hosting a node
should use a fixed IP. That's the cost of prioritization/reward. The
protocol could be a service bit, advertised in the version message.

My response to your comment below:

On 27/03/2015 03:40 p.m., Jeremy Spilman wrote:
>
> It would be extremely impressive to achieve a reliable mechanism for 
> discerning a local copy exists under these constraints, particularly without 
> false positives and false negatives, and without imposing very substantial 
> one-time encoding costs, e.g. on par with doubling the verification cost. 
I see it differently. The asymmetric-time protocol is quite reliable. If
can be made to have almost no false positives/false negatives (not
considering rare communication problems, such as congestion and packet
loss for more than 5 seconds).
These are my back-of-the-envelope calculations:
Bitcoind takes approximately 1 second to serve a 1 Mb block (seek time,
but mostly transfer time)
Then decryption of a block can take 150 msec without problem (15%
overhead). The last N blocks could be cached so they don't need to be
decrypted to be sent.
In 150 msec a PC can decrypt a 1MB of data split over 1024-bit blocks
decrypted by modexp 3 (0.2 msec for 3 bigint multiplications), so a full
block can be decrypted.
Encrypting such block would take approximately 15 seconds (which is much
less than the 10 minutes available to encrypt each block)
Then the protocol works with a security margin of approximately 50x.
A communication problem during 5 seconds would be needed to disturb a
protocol of that takes 100 msec for the prover.

Regards,
 Sergio.



--
Dive into the World of Parallel Programming The Go Parallel Website, sponsored
by Intel and developed in partnership with Slashdot Media, is your hub for all
things parallel software development, from weekly thought leadership blogs to
news, videos, case studies, tutorials and more. Take a look and join the 
conversation now. http://goparallel.sourceforge.net/
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] "network disruption as a service" and proof of local storage

[Sergio Lerner]

> If I understand correctly, transforming raw blocks to keyed blocks
> takes 512x longer than transforming keyed blocks back to raw. The key
> is public, like the IP, or some other value which perhaps changes less
> frequently.
>
Yes. I was thinking that the IP could be part of a first layer of
encryption done to the blockchain data prior to the asymetric operation.
That way the asymmetric operation can be the same for all users (no
different primers for different IPs, and then the verifiers does not
have to verify that a particular p is actually a pseudo-prime suitable
for P.H. ) and the public exponent can be just 3.

>
>> Two protocols can be performed to prove local possession:
>> 1. (prover and verifier pay a small cost) The verifier sends a seed to
>> derive some n random indexes, and the prover must respond with the hash
>> of the decrypted blocks within a certain time bound. Suppose that
>> decryption of n blocks take 100 msec (+-100 msec of network jitter).
>> Then an attacker must have a computer 50 faster to be able to
>> consistently cheat. The last 50 blocks should not be part of the list to
>> allow nodes to catch-up and encrypt the blocks in background.
>>
>
> Can you clarify, the prover is hashing random blocks of *decrypted*,
> as-in raw, blockchain data? What does this prove other than, perhaps,
> fast random IO of the blockchain? (which is useful in its own right,
> e.g. as a way to ensure only full-node IO-bound mining if baked into
> the PoW)
>
> How is the verifier validating the response without possession of the
> full blockchain?

You're right, It is incorrect. Not the decrypted blocks must be sent,
but the encrypted blocks. There correct protocol is this:

1. (prover and verifier pay a small cost) The verifier sends a seed to
derive some n random indexes, and the prover must respond with the the
encrypted blocks within a certain time bound. The verifier decrypts
those blocks to check if they are part of the block-chain.

But then there is this improvement which allows the verifier do detect
non full-nodes with much less computation:

3. (prover pays a small cost, verifier smaller cost) The verifier asks
the prover to send a Merkle tree root of hashes of encrypted blocks with
N indexes selected by a psudo-random function seeded by a challenge
value, where each encrypted-block is previously prefixed with the seed
before being hashed (e.g. N=100). The verifier receives the Markle Root
and performs a statistical test on the received information. From the N
hashes blocks, it chooses M < N (e.g. M = 20), and asks the proved for
the blocks at these indexes. The prover sends the blocks, the verifier
validates the blocks by decrypting them and also verifies that the
Merkle tree was well constructed for those block nodes. This proves with
high probability that the Merkle tree was built on-the-fly and
specifically for this challenge-response protocol.

> I also wonder about the effect of spinning disk versus SSD. Seek time
> for 1,000 random reads is either nearly zero or dominating depending
> on the two modes. I wonder if a sequential read from a random index is
> a possible trade-off,; it doesn't prove possession of the whole chain
> nearly as well, but at least iowait converges significantly. Then
> again, that presupposes a specific ordering on disk which might not
> exist. In X years it will all be solid-state, so eventually it's moot.
>
Good idea.

Also we don't need that every node implements the protocol, but only
nodes that want to prove full-node-ness, such as the ones which want to
receive bitnodes subsidy.



--
Dive into the World of Parallel Programming The Go Parallel Website, sponsored
by Intel and developed in partnership with Slashdot Media, is your hub for all
things parallel software development, from weekly thought leadership blogs to
news, videos, case studies, tutorials and more. Take a look and join the 
conversation now. http://goparallel.sourceforge.net/
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] "network disruption as a service" and proof of local storage

[Sergio Lerner]

The problem of pseudo-nodes will come over and over. The cat and mouse
chase is just beginning.
It has been discussed some times that the easiest solution world be to
request some kind of resource consumption on each peer to be allowed to
connect to other peers.
Gmaxwell proposed Proof of Storage here:
https://bitcointalk.org/index.php?topic=310323.msg3332919#msg3332919

I proposed a (what I think) is better protocol for Proof of Storage that
I call "Proof of Local storage" here
https://bitslog.wordpress.com/2014/11/03/proof-of-local-blockchain-storage/
. It's better because it does not need the storage of additional data,
but more importantly, it allows you to prove full copy of the blockchain
is being maintained by the peer.
This is specially important now that Bitnodes is trying a full-node
incentive program that may be easily cheated
(http://qntra.net/2015/02/pseudonode-proxy-fools-bitcoin-full-node-incentive-program/)

Proof of local storage allows a node to prove another peer that he is
storing a LOCAL copy of a PUBLIC file, such as the blockchain. So the
peer need not waste more resources (well, just some resources to
encode/decode the block-chain).
The main idea is to use what I called asymmetric-time-encoding.
Basically you encode the block-chain in a way that it takes 100 more
times to write it than to read it. Since the block-chain is an
append-only (write-only) file, this fit good for our needs. For instance
(and as a simplification), choosing a global 1024-bit prime, then
splitting the block-chain in 1024-bit blocks, and encrypting each block
using Polihg-Hellman (modexp) with decryption exponent 3.  Then
encryption is at least 100 times slower than decryption. Before PH
encryption each node must xor each block with a pseudo-random mask
derived from the public IP and the block index.  So block encryption
could be: 
BlockEncryptIndex(i) = E(IP+i,block(i))^inv(3) (mod p),

where inv(3) is 3^-1 mod (p-1). E() could be a fast tweaked encryption
routine (tweak = index), but we only need the PRNG properties of E() and
that E() does share algebraic properties with P.H..

Two protocols can be performed to prove local possession:
1. (prover and verifier pay a small cost) The verifier sends a seed to
derive some n random indexes, and the prover must respond with the hash
of the decrypted blocks within a certain time bound. Suppose that
decryption of n blocks take 100 msec (+-100 msec of network jitter).
Then an attacker must have a computer 50 faster to be able to
consistently cheat. The last 50 blocks should not be part of the list to
allow nodes to catch-up and encrypt the blocks in background.

2. (prover pay a high cost, verified pays negligible cost). The verifier
chooses a seed n, and then pre-computes the encrypted blocks derived
from the seed using the prover's IP. Then the verifier sends the  seed,
and the prover must respond with the hash of the encrypted blocks within
a certain time bound. The proved does not require to do any PH
decryption, just take the encrypted blocks for indexes derived from the
seed, hash them and send the hash back to the verifier. The verifier
validates the time bound and the hash.

Both protocols can me made available by the client, under different
states. For instance, new nodes are only allowed to request protocol 2
(and so they get an initial assurance their are connecting to
full-nodes). After a first-time mutual authentication, they are allowed
to periodically perform protocol 1. Also new nodes may be allowed to
perform protocol 1 with a small index set, and increase the index set
over time, to get higher confidence.

The important difference between this protocol and classical remote
software attestation protocols, is that the time gap between a good peer
and a malicious peer can be made arbitrarily high, picking a larger p.
Maybe there is even another crypto primitive which is more asymmetric
than exponent 3 decryption (the LUC or NTRU cryptosystem?).

In GMaxwell proposal each peer builds a table for each other peer. In my
proposal, each peer builds a single table (the encrypted blockchain), so
it could be still possible to establish a thousands of connections to
the network from a single peer. Nevertheless, the attacker's IP will be
easily detected (he cannot hide under a thousands different IPs). It's
also possible to restrict the challenge-response to a portion of the
block-chain, the portion offset being derived from the hash of both IP
addresses and one random numbers provided by each peer. Suppose each
connection has a C-R space equivalent to 1% of the block-chain. Then
having 100 connections and responding to C-R on each connection means
storing approximate 1 copy of the block-chain (there may be overlaps,
which would need to be stored twice) , while having 1K connections would
require storing 10 copies of the blockchain.


Best regards,
 Sergio


--
Dive into the World of Para

Re: [Bitcoin-development] BIP: Voluntary deposit bonds

[Sergio Lerner]

On 30/12/2014 01:51 a.m., Gregory Maxwell wrote:
> On Mon, Dec 29, 2014 at 7:21 PM, Sergio Lerner
>  wrote:
>> I propose to allow miners to voluntarily lock funds by letting miners
>> add additional inputs to the coinbase transaction. Currently the
>> coinbase transaction does not allow any real input  to be added (only a
>> pseudo-input).
>>
>
> To make that more concrete.  E.g. You make your anyone can spend
> output   "PUSH OP_NOP3".  Now
> this anyone can pay transaction is really just a coinbase input.

Slight off-topic:
That looks like an abuse of the VM. Even P2SH is an abuse of the VM.
Gavin's OP_EVAL (hard-fork) should had been chosen. I'm taking about a
simple change that goes along the lines of Satoshi's original design.
Bitcoin was a beautiful design, and extra complexity is making it ugly.
We need Bitcoin to be simple to understand for new programmers so they
can keep the project going. It doesn't help the project that one needs
to be a guru to code for Bitcoin.

--
Dive into the World of Parallel Programming! The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] BIP: Voluntary deposit bonds

[Sergio Lerner]

I propose to allow miners to voluntarily lock funds by letting miners
add additional inputs to the coinbase transaction. Currently the
coinbase transaction does not allow any real input  to be added (only a
pseudo-input).
This is a hard-fork, and we could include it the next time a hardfork is
made.
The modifications to the code are minimal (no more than 12 lines
modified where IsCoinBase() is called), and they generally involve
removing code, not adding.

Why ?

Because sometime in the future (maybe 5-10 years) we may have to deal
with problems of securing the blockchain, as the subsidy is lowered. We
don't want the number of confirmation blocks to be increased in
compensation because Bitcoin won't be able to compete with other payment
networks.
Then by having this hardfork now, we will be able to soft-fork later to
any rule we may came come up with involving deposit bonds,
proof-of-stake, and the penalization of double-mining (mining two blocks
at the same height) to prevent short-range attacks.

Can it hurt?

No. I doesn't not change the incentives or the security in any way, as
adding additional inputs to the coinbase transaction would be voluntary
until the time for a soft-fork comes.
We shouldn't hard-fork for this change only, but maybe we could do this
change when the next hard-fork is scheduled (when we increase the block
size?).

Regards, S.









--
Dive into the World of Parallel Programming! The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] ACK NACK utACK "Concept ACK"

[Sergio Lerner]

Is that the full terminology or are there more acronyms?
Is this documented somewhere?

Best regards,
 Sergio.



--
Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
from Actuate! Instantly Supercharge Your Business Reports and Dashboards
with Interactivity, Sharing, Native Excel Exports, App Integration & more
Get technology previously reserved for billion-dollar corporations, FREE
http://pubads.g.doubleclick.net/gampad/clk?id=164703151&iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] Death by halving (pro-active proposals)

[Sergio Lerner]

Instead of discussing what will happen when the subsidy is halved (which
nobody really knows) maybe we can think about of what we can do to
mitigate any damage in case something unwanted happens. Let's be proactive.

For instance, any form of merged-mining (like higher frequency
side-chains) will end-up increasing miners profit, even by a small
margin. Then that margin can compensate miners not to turn off their
equipment. Then we can encourage merge-mining on SHA-256, instead of
discouraging SHA-256 alt-coins.

Also we can encourage mining during the "trouble" period by creating a
donation pool: suppose we manage to convince miners to donate 1% of
their revenue in order to pay back to the miners for the first month
after the reward halving. If every block pays 1% for 10 months, then
every block during the first month of halving will earn 20% more.  Of
course, convincing miners of this may be difficult, but not impossible.
It could be done automatically with nLockTime freeze of transactions
with high fees, so no TTP is necessary.

So here are two proposals, any other idea?

Best regards,
 Sergio.



--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

On 07/10/2014 04:16 p.m., Gregory Maxwell wrote:
> Then I spend the output of the fraudulent spend nlocked
> one block higher, and spend the output of that one again, nlocked one
> block higher, and so on... each step paying fees.
Yes, you're right. I didn't consider that case. But the problem is that
this is not automatic. Currently there is a clear division between
miners how will not take the kickback (irrrational) and miners who will
(rational).
If somebody modifies the bitcoind to make this choice automatic, then
DECOR+ is the only solution I know about to avoid people doing anonymous
double-spends (with chained kickbacks, as you mention).
The  "locktime on normal transactions" you proposed does not solve the
problem, just diminishes it in a constant value (which currently is very
low)




--
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

On 06/10/2014 08:43 p.m., Tom Harding wrote:
> On 10/5/2014 4:00 PM, Sergio Lerner wrote:
>> If everyone acts rationally in his own interest, then the best choice
>> for the remaining miners is to try to mine a competing block at the
>> same height n including the high-fee transaction, to collect the fee
>> for themselves.
>
> Sergio --
>
> Just some thoughts on your interesting problem.
>
>
> Since everybody but M10 is on equal footing, I would expect M10 to
> have some fixed advantage depending on assumptions, and the bigger the
> advantage, the shorter the "freeze time".
>

Yes, that's how simulation works. The problem is that the existence of
high-fee delays the decision to switch to M10. Since the network is
moving slower (because of fragmentation) the effect of the high-fee is
twofold: it delays the convergence because it promotes selfishness and
it delays convergence because it promotes fragmentation.

During that time window where the network is frozen, any other high-fee
transaction only makes things worse.  This is a very rare example where
a well distributed network (100 miners having 1% each) is much much
worse than 3 miners having 33% each.

Using the my previous terminology, automatic fee-sharing ("ORBS") is a
solution to the freeze problem ("FRONT") but opens the windows to
"CHAKIDO" double-spending. and CHAKIDO double-spending is a much worse
problem than FRONT.
But as Tamas pointed out, sooner or later someone will implement
something like ORBS, get over the critical mass of miner adoption, and
then the CHAKIDO problem will be inevitable.

The only clean solution to this problem is the DECOR+ protocol, which
shares block-rewards by including "uncles" (as GHOST does) and splitting
the reward between all miners at the same height until coinbase maturity
is over. This way the best choice is always cooperative.

PS: Using so many acronyms makes arguments much more concise, but
suggest we should have all the attack terminology described in a single
"Bitcoin Security Wiki"...














--
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

Comments between lines...

On 06/10/2014 03:42 a.m., Alex Mizrahi wrote:
> .
>
> This doesn't require protocol changes(*) and can be simply
> incorporated into a piece of code which decides what to do when a
> transaction with unusually large fee appears. (I.e. it will
> automatically share the fee, and others will recognize that). And if
> the biggest miner has 25% of all hashrate, sharing 25% of your loot
> doesn't sound that bad.
The problem with this approach is that once the bitcoind has been
modified to allow this sharing of the high-tx fee by delegation, then
the same system can be used for an attack.
Let's call a system that makes the Optimum Rational Best-chain Selection
for maximizing profit "ORBS", just to give it a name. The system assures
that the best chain chosen is always the optimum in terms of profit,
taking into account fee delegation and all the game-theoretic incentives
derived. It's only a theoretical abstraction, but could be approximated
in practice.

The attack is called Chained Kickback DOuble-spend attack (or “CHAKIDO”)
and is an extension of Bonneau's kickback attack. Basically the attack
is to create the ORBS patch, and start convincing miners to use it,
sending some probe high-fees tx.
Once you have ORBS working in a majority of the mining nodes, you can
perform a double-spend against a target like an exchange by:
- Buy some btc X
- Send those btc to an exchange (suppose the exchange requires 6
confirmations) in a transaction TX
- Immediately convert those btc to an alt-coin, and collect the alt-coins
- Create a high fee tx that is a double-spend of TX having a high fee Y
such that Y < X but Y triggers a ORBS reorganization.
- Profit
(This rollback attack was performed against whitecoin, I think)

This attack gets terrible powerful if there is no subsidy. You may need
500 blocks of confirmation to protect from a 10 BTC spend with current
fees and no subsidy. This is because once 100% of the nodes use ORBS,
the fee delegation is linear (it doesn't grow exponentially with the
number of blocks). So ORBS should never be implemented without
additional protective measures in merchant applications.
If we had a closed formula for ORBS, then all merchants could compute
the minimum confirmation blocks such that always Y > X, but such formula
involves many unknowns which would need to be dynamically estimated, and
also it should take into account the number of simultaneous payment
attempts.

My conclusions are:
- We should never allow ORBS to be implemented unless merchants are also
aware of it. If are aware of ORBS then Bitcoin with no subsidy will be
become a terrible slow payment system so ...
- We could implement the protections that work even if some nodes
implement ORBS, such as fee and burn btc sharing, as I described before
- Or we need some high percentage of miners to be irrational, to force
ORBS fee delegation have an exponential decay.

Best regards,
Sergio.

--
Slashdot TV.  Videos for Nerds.  Stuff that Matters.
http://pubads.g.doubleclick.net/gampad/clk?id=160591471&iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] The Bitcoin Freeze on Transaction Attack (FRONT)

[Sergio Lerner]

I would like to share with you a vulnerability in the Bitcoin protocol
I've been thinking of which might have impact on the future of Bitcoin.
Please criticize it!

*The Freeze on Transaction Problem
*

The freeze problem occurs if someone publishes a transaction with fees
much higher than the block subsidy. I don't remember who described the
attack first. Suppose that, by mistake, a transaction is published with
50 BTC in fees. The transaction is included in a block at height n. If
everyone acts rationally in his own interest, then the best choice for
the remaining miners is to try to mine a competing block at the same
height n including the high-fee transaction, to collect the fee for
themselves. All the miners having solved the block at height n, now move
on mining at height (n+1). But they won't choose each other branches
until one branch is sufficiently longer so that it is better to switch
to it and abandon their own branch rather than try to keep the block
with the high fee. This case is different from the real block
competition case we see periodically on the blockchain, where the miners
are generally split between two branches. Here there are multiple
branches competing. If there are 10 "top" miners each having 10% of the
network hashing power, then 10 different branches will compete. The
analysis for this case is similar to the Gambler's Ruin problem analysis
present in the Satoshi paper, but with a fixed constant monetary
incentive not to switch. Since the incentive to switch grows
exponentially with the branch length difference, any initial constant is
diluted. In the special and rare case that all the miners have exactly
the same hashing power, then the network diverges, and this is
equivalent as having two miners having exactly 50% of the hashing power
each. So in principle the freeze on transaction problem is just a
temporary disruption in the network, but not a fatal halt. Nevertheless,
since during the freeze period each miner is mining on his own branch,
it also means that moving forward with blocks is a lot slower. Assuming
10 miners having 10% of the total hashing power each (+/- 3%), the
network becomes 10 times slower. I simulated it with a 50 BTC tx freeze
fee, and 10 miners, and it takes approximately 6 blocks to converge, so
the freeze time is approximately 60 times the block interval, or 10
hours. If the distribution is approximately 25% of the hashing power for
each top miner, the freeze time is 4 hours.

Obviously what's needed for the freeze problem to occur is that miners
are 100% rational, greedy and prepared. They need to have a modified
version of bitcoind which can automatically detect a high-fee
transaction and prevent adding to the best chain a not-owned block
containing such transaction. There will be no time for the miners to
patch bitcoind if such transaction is manually spotted. Also the latest
versions of bitcoind have preventions not to allow high fees by mistake.
So the freeze problem is currently non-existent, but may pop up in the
future in form of a state-sponsored attack.

*The Freeze problem as an Attack*

If an attacker plans to repeat such attack periodically at the expense
of wasting a lot of BTC, there is little the current protocol can do,
because miners will be prepared to take advantage of the attack. If the
attacker issues a new fee burning transaction before the network
converges, then the attacker can maintain incentives to keep every miner
separated in his own branch. So wasting 50 BTC every 4 hours, an
attacker can maintain the network frozen forever.  Even if we restrict
the maximum fee per transaction, the scripting system has infinite ways
to create transactions whose output can be taken by anyone, and the
attacker can announce the method miners can use to collect those BTC and
even prepare and publish the bitcoind patches to automate collecting
those transaction outputs.

The best thing the community can do is act together and cooperate to
share the high transaction fee. This will neutralize the attack
completely and allow miners to earn extra bitcoins. But cooperation in
the Bitcoin community has never been easy. There is a technical solution
which is to modify the Bitcoin protocol so that every transaction output
has a maturity time of 6 blocks, and if a transaction output is redeemed
multiple times in a 6 block interval, then the BTC amount is split
between all redeemers, and also fees would be automatically shared in a
6 block sliding window. At a first glance, this provides a way for
miners to cooperate even anonymously and there is no immediate drawback,
but an in depth analysis is necessary.

--
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analy

Re: [Bitcoin-development] [BIP draft] CHECKLOCKTIMEVERIFY - Prevent a txout from being spent until an expiration time

[Sergio Lerner]

I like the proposal.

I suggest that applications and nodes should only broadcast transactions
having OP_CHECKLOCKTIMEVERIFY a few blocks after the timeout value.
If a node broadcasts a TX having OP_CHECKLOCKTIMEVERIFY and nLockTime is
equal to the current height and equal to the timeout value, but that
peer is one block behind in the blockchain, the transaction will be
rejected by the peer and the source will be banned.

Another option will be not to ban peers sending transactions failing to
verify OP_CHECKLOCKTIMEVERIFY , but I don't like this.

Still another option would be that the sender checks periodically the
height of it's peers (using the version command) in order to be sure to
send the transaction having OP_CHECKLOCKTIMEVERIFY only to the peers
that are up to date with the blockchain.

Regards,
 Sergio.




--
Meet PCI DSS 3.0 Compliance Requirements with EventLog Analyzer
Achieve PCI DSS 3.0 Compliant Status with Out-of-the-box PCI DSS Reports
Are you Audit-Ready for PCI DSS 3.0 Compliance? Download White paper
Comply to PCI DSS 3.0 Requirement 10 and 11.5 with EventLog Analyzer
http://pubads.g.doubleclick.net/gampad/clk?id=154622311&iu=/4140/ostg.clktrk
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] Improvement to the Test Framework in the processing of test blocks

[Sergio Lerner]

We've coded and tested changes to the Bitcoin testing framework to allow
the creation and processing of blocks in unit test cases in order to
test ProcessBlock(), CheckBlock(), ActivateBestChain(),
ActivateBestChainStep() and ConnectTip(), including block-chain
reorganizations, majority rules, block version changes and more.
Several new test cases were added to enrich the test suite.

Please review and comment the pull request:

https://github.com/bitcoin/bitcoin/pull/4688

Best regards,
 Sergio Demian Lerner & Timo Hanke

--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] CoinShuffle: decentralized CoinJoin without trusted third parties

[Sergio Lerner]

Hi Tim,
 It's clear from the paper that the second party in the protocol can
de-anonymize the first party. So it's seems that dishonest shufflers
would prefer to be in that position in the queue.
There are two possible solutions to this:

1. Derive the first order of parties in the shuffle from the hash of all
inputs provided (as a seed for a pseudo-random number generator).
2. Repeat the shuffle several times with an different party order (e.g.
an order that is deterministically derived from the hash of all the outputs)


Best regards,
 Sergio/


On 09/08/2014 07:04 a.m., Tim Ruffing wrote:
> You are raising valid questions and one goal of our posting here is indeed to 
> discuss exactly these system issues.
>
> On Thursday 07 August 2014 15:00:11 you wrote:
>> I think the description at your website leaves out the truly interesting
>> part: How do you decentralize this securely?
>> - How do Alice, Bob, Charlie and Dave communicate, i.e. which network is
>> used for communication and how?
> The simplest approach is obviously to use direct connections to a randomly 
> elected leader, who is also responsible for the broadcasts.
> One advantage of CoinShuffle is that the unlinkability between input and 
> output addresses is guaranteed, no matter which underlying network you use. 
> (Still, it is a good idea in general to hide your IP address but we can let 
> the user decide here.)
>
> Of course, there would be other possibilities, such as overlay networks. 
> Coinmux, a CoinJoin prototype by Michael Pearce (http://coinmux.com/) uses 
> TomP2P, a distributed hash table, for communication. 
>
> Do you have any hints regarding this point?
>
>> - How does Alice know that Bob, Charlie and Dave are not the same person?
>> (= how do you prevent a Sybil attack?)
>>
>> Because thats the real problem with mixing it seems - ensuring that your
>> mixing partners are actually 100 people and not just 1 attacker. There are
>> probably many mixing algorithms which work if you solve that problem, but I
>> don't see how you offer a solution for it :(
> It's true that there are a few proposals for mixing protocols which all have 
> their advantages and disadvantages. However, it's not true that the mixing 
> itself becomes simple if you solve the problem of Sybil attacks. Still, 
> mixing 
> is difficult to get right: Even if there are no Sybil attacks, you have to 
> ensure that the participants (or a server) cannot break unlinkability or 
> steal 
> money. Actually that's why there are several proposals for mixing protocols, 
> because there is no obvious perfect solution.
>
> Regarding your question:
> It is indeed very important to get this right. Fundamentally, there is 
> nothing 
> that prevents the attacker from creating a lot of identities participating in 
> a lot of CoinJoins. However, there are ways that make it hard for the 
> attacker 
> to put an honest user together only with malicious users.
>
> For a moment, assume that you can reliably establish a pool of users that 
> would like to participate in the protocol. (I will discuss this later.) 
> You have to divide the users to individual groups, i.e., CoinJoins runs. If 
> the assignment cannot be influenced by the attacker, then the probability 
> that 
> there are also honest users in a run is quite high. Of course, the attacker 
> is 
> able to reduce your anonymity set but they cannot just put you together only 
> with their malicious identities.
>
> Note that the attacker has to pay transaction fees for joining many 
> transaction. One could even increase the required fee depending on the number 
> of users in the pool (enforced by honest CoinShuffle participants that would 
> not accept CoinJoins that pay a lower transaction fee).
>
> And making sure that the attacker cannot influence the assignment is simple: 
> One can use the hash of all users' public keys in the pool to determine the 
> assignment for example.
>  
> For the initial setup step, i.e., creating the pool of participants, you need 
> some kind of "bulletin board". 
>
> One possibility is to use an underlying peer-to-peer network. Bitcoin itself 
> is the first that comes to the mind but it does not allow arbitrary messages. 
> So if we do not want to change the Bitcoin protocol, chans in Bitmessage are 
> a 
> very promising possibility. Bitmessage relies basically on the same broadcast 
> mechanism as Bitcoin. If you as a peer use enough outgoing connections to 
> other peers, it's very difficult for an attacker to ensure that your message 
> will not be spread among the network. (Btw, people have used this to do 
> CoinJoin  manually already 
> https://forum.namecoin.info/viewtopic.php?f=2&t=1694 .)
> Solutions like distributed hashtables (TomP2P again) are another possibility. 
> We are not sure which of those approaches provides the best robustness 
> against 
> malicious nodes that try to stop single participants from reaching the 
> network. For the setup step, latency is not an is

Re: [Bitcoin-development] Miners MiTM

[Sergio Lerner]

Since the information exchanged between the pool and the miner is
public, all that's needed is a mutual private MAC key that authenticates
messages.
This requires a registration step, that can be done only once using a
simple web interface over https to the miner website.
But the miner website is not the miner server, so the worst DoS would be
preventing new miners to join the pool, which is not very often.
The MAC key can be provided directly by the miner. And the pool
associates the MAC key with a Bitcoin public address.
The overhead would be minimal.


-Sergio.


--
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] Question on creating test cases for block.CheckBlock()

[Sergio Lerner]

I'm working on a BIP which needs to modify the block acceptance rules. I
have two ways of testing:

- Mining blocks on the testnet
- Creating test cases for Bitcoin Core.

I want to create those test cases for block.CheckBlock(), which involves
verifying 100 dynamically generated blocks.
What is the state of the blockchain when a test case is executed ? Is is
configured for the regtest, testnet3 or mainnet? What blocks are in the
blockchain? Only the genesis block?

checkblock_tests.cpp seems to be the only test case for CheckBlock() and
it assumes the mainnet is configured.
I need to use the regtest so I can create blocks of difficulty 1.

Best regards and thank you in advance,


--
Want fast and easy access to all the code in your enterprise? Index and
search up to 200,000 lines of code with a free copy of Black Duck
Code Sight - the same software that powers the world's largest code
search on Ohloh, the Black Duck Open Hub! Try it now.
http://p.sf.net/sfu/bds
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] BlockPow: A Practical Proposal to prevent mining pools AND reduce payoff variance:

[Sergio Lerner]

I propose a setting that prevent mining pools AND reduce payoff variance
which requires two changes: increasing the block-rate and changing the
Bitcoin PoW (but still allowing current Bitcoin ASICs to work (as far as
I know)). The block rate must be increased at least 20 times and block
must still be near full (e.g. there must be at least 20 more
transactions/second than there is today)

BlockPow is kind of PoW that only practically prevents mining pools for
certain cryptocurrency settings based on concepts similar to parmacoin,
but in a much simple degree. The idea is that if miners try to join a
pool, then they incur in overhead of transmitting information and earn
less than working solo. Let b (the payload) contain a full block. b must
contain all the transactions and the header, and not only the
transaction hashes. b should not hide anything. Let h be the block
header (which contains the previous block hash and the Merkle tree root
of the transactions). Let d be the difficulty. hash-block-length(b)
returns the number of blocks processed by the hash function when fed
with the block b. The target is divided by hash-block-length(b) so that
the difficulty does not depend on the length of the block. Some other
function can be used to encourage nodes to add more or less transactions.

Def: Basic BlockPoW concept

For each r in the nonce-range: if H ( H( r || b ) || h || r) ) < 2^-d/
hash-block-length(b) then return r

return null

The header (h) is appended to the hashed message to allow SPV clients to
verify the PoW without requiring the full block to be downloaded. Peers
can send only (x,r,h) to SPV nodes, where x = H( r || b ), so they can
verify the PoW. The verification procedure is obvious, and is skipped
here. r is inserted at the beginning of the message to prevent pool
administrators from keeping a secret mid-state of the hash function
secret in order to prevent block stealing and also to force the miner to
know b in the inner mining loop.

So now mining requires the knowledge of the block b to be mined, and b
must be received at each block-chain epoch. This could create an
incentive not to include any transaction and use an almost empty b,
because that way the bandwidth requirements is decreased. But this
incentive should not exists normally, since by including transactions
the solo miner gets an additional revenue from fees, which is lost if
the block is empty. Anyway, to prevent this possible incentive we can
append to b a subset of previous blocks (e.g 100 blocks). The block
subset to include could be derived from a peudo-random function seeded
by the previous block hash. Then a node would still need to download
part or all the block-chain in order to mine.

Now if the miner wants to be a dumb node and take part of a pool, then
the current working unsolved block (the template) must be sent each time
from the pool admin to each miner. If the pool admin hosts 1000 miners,
then to serve them with fresh block templates he needs 1000 times more
bandwidth that the miners, making this much more expensive. If miners
create another network topology to distribute templates, they are
incurring in the same overhead as being actively part of the
cryptocurrency network, so they gain nothing.

For example, in a block-chain with a 5 seconds block-rate, such as in
NimbleCoin , each block can be as large as 200
Kbytes (100 tps are allowed). A miner will require the block template to
be ready as fast as possible, say before 3 seconds, so as not to loose
more than 60% of the times the transaction fees present in the block
template. This means that a pool admin serving 1000 clients must have a
upload bandwidth of at least 60 Mbytes/sec, and load balance servers,
because all miners will demand the block template at the same time and
will compete for it.

The same miner, working solo, will not loose the 60% of block fees. If
block fees are 10% of block reward, then solo miners earn 6% more than
pool miners. Also, having a block rate of 5 seconds allows solo miners
to receive payments more often and so it reduces the payment variance.

This method to discourage mining pools only work as long as time is
takes to transmit a block is comparable to the block interval time, e.g.
20%. This seems not to be a problem since if the cryptocurrency becomes
popular, then we can expect blocks to be near full, while if is is not,
then nobody will care about mining pools.

For this method to work for Bitcoin, Bitcoin should reduce the block
rate to at least 1 minute, and keep blocks of at least 10 Mbytes. Or go
the NimbleCoin way, and reduce the block interval to 5 seconds. The sole
reduction of the block rate from 10 minutes to 5 seconds would reduce
notably the mining reward variance, which is the main reason miners
don't mine solo.

BitcoinBlockPow

The basic BlockPoW is incompatible with Bitcoin ASICs as is but it can
be made partially compatible with some tweaks: The value b is replaced
by a a a subset or a

Re: [Bitcoin-development] Paper Currency

[Sergio Lerner]

Alex,

I think that what you are talking about more or less something like
the Firmcoin

Check: http://firmcoin.com/?p=92


On 18/05/2014 08:47 a.m., Alex Kotenko wrote:
>
>
> One problem we couldn't figure out here though - how to protect the
> notes from unauthorized redeem. Like if someone else tries to reach
> your wallet with his own NFC - how can we distinguish between
> deliberate redeem by owner and fraudulent redeem by anybody else with
> custom built long range NFC antenna? Any ideas?
>
>
The firmcoin has two capacitive buttons that you have to press in
sequence to redeem to coins. No long range antenna can do that.

Best regards,
 Sergio.

PS:   the device has patents pending
--
"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos.
Get unparalleled scalability from the best Selenium testing platform available
Simple to use. Nothing to install. Get started now for free."
http://p.sf.net/sfu/SauceLabs___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] DECOR+ Better block selection rule

[Sergio Lerner]

This e-mail is an extract of my post:
http://bitslog.wordpress.com/2014/05/07/decor-2/

Some posts ago I presented the DECOR protocol. One of the assumptions I
did was that the amount of coins each miner earned in competing blocks
was approximately the same. This could be true for cryptocurrencies with
never ending block subsidies (inflationary designs) because the block
subsidy may be an order of magnitude higher than the fees collected in
the block. In Bitcoin we don’t really know what will happen with fees
when the reward is halved. Less we know if in that case the number of
transactions per block (and fees collected) will be fairly constant or
there will be high variability. If Alice and Bob compete for a certain
block height with blocks A and B respectively, and Alice’s block reward
(subsidy+fees) is half of Bob’s reward, then even if Hash(A) < Hash(B)
(and the DECOR incentives are set to prefer A) it may be the case that
both Alice and Bob would prefer to mine on top of B since they both earn
much more even paying the higher penalty d of burnt coins. In limit
cases, Alice’s optimal choice may not be the same as Bob’s optimal
choice. I propose a slight modification of the protocol such that even
with different block rewards the optimal choice of parent is always the
same for all miners. Instead of choosing the block with less hash
digest, miners will choose the block with higher reward (subsidy+fees).
Splitting the higher reward block would always be more profitable than
splitting lowest reward block. In the rare case both blocks have exactly
the same reward, then the block with lowest hash is chosen. Even if
rewards are approximately equal, the change adds a new monetary
incentive to cooperate. Compared with the DECOR protocol, the only
modification is in step 6.

*DECOR+ Mining strategy*

 1. If there is no block Y having a sibling X in the main chain whose
reward has not matured then mine in the standard way and exit this
procedure
 2. Add a reference to Y in the new block that is being prepared.
 3. Let x  := BlockReward(X)
 4. Let q := x*a
 5. Let z :=x*b
 6. If (BlockReward(X)Hash(Y)) then
q :=q-(x*c)
z :=z+(x*d)
 7. Let w :=x*e
 8. Add a transaction that has as input the coinbase output of X and has
four outputs:
  o pay q coins to the address specified in the coinbase output
of block Y
  o pay w coins to an owned address
  o burns z coins
  o pay the remaining coins to the same address as the input
address.

 

BlockReward() returns the block subsidy plus the transaction fees in the
block.

*Conditions on constants*

If you want to choose different values of a,b,c,d,e that still force
miners selections converge into a single parent then these conditions
must be satisfied:

  * e > 0
  * 1-a-e-b > a-c
  * 1+e-a-e-b > a-c
  * a > 1-a-c-e-b-d
  * a+e > 1-a-c-e-b-d

And all constants are between 0 and 1.

It's interesting that now it's much easier to prove that for two
competing miners the DECOR+ protocol cannot be abused, since there is no
dependence on the block content.

Best regards,
 Sergio.
--
Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Block collision resolution using the DECOR protocol and Bonneau's Kickbacks problem

[Sergio Lerner]

On 02/05/2014 10:56 a.m., Joseph Bonneau wrote:
> This is an interesting idea Sergio. I have two concerns:
>
> You mention "50% of the block reward" going to the uncle block. Does
> this mean the parent gets 1, and the uncle 0.5, or both get 0.5? In
> the first interpretation (which I assumed was the design), mining is
> no longer a zero-sum game and this could have lots of unforeseen
> implications. For example, selfish mining might be more profitable,
> since you're less disincentivized to avoid conflicts.
The second interpretation is the correct one.
> In the second interpretation, there's pressure to have the next miner
> ignore the uncle to not share the reward. This would encourage
> kickback-style attacks and advantage large mining pools because they
> can mine on their own blocks and ignore colliding uncles.
Including an uncle can be done at any time before a coinbase matures
(100 blocks) (of course the term "uncle" is misleading in those cases) .
So, for example, the uncle can be included 50 blocks afterward. So it's
very difficult that a miner prevents other miners from including the
uncle and taking the reward given by uncle inclusion.

Same ineffective attack:
A big miner could try to bribe all other miners not to include the
uncle, but this would be terribly costly. Suppose that I mine a block
ignoring an uncle Z and then I publish this message: "Every miner from
block number X to block number Y that does not include this uncle Z will
be given Q Bitcoins". How much would Q be? Since by including the uncle
the miner gets 5 BTC of reward (in the example case where block reward
is 50 BTC), then each bribery payment would have to be higher than 5
BTC, totaling 500 BTC ! much more than the 25 BTC the miner will loose
by including the uncle.

Just by sending a transaction with a lot of fees that depends on my
block does not prevent subsequent miners from including the supposedly
banned uncle.

Then, I think there are no kickback-style attacks.

>
> Also, I think this came up in the Princeton meet-up, but it's not
> ideal to just hash the blocks to decide the "winner" because this lets
> you know in advance your block's likelihood of winning a collision by
> looking at how high or low its hash is, in which case you can publish
> a weak block right away or withhold a strong one and do selfish
> mining. A better approach to break ties between blocks A and B is to
> see if H(A||B) < H(B||A). That way neither block holder can find out
> in advance if their block is likely to win a collision.
>
In the DECOR protocol, I think selfish miners cannot get any advantage,
because the blocks that loose the latency race will come back as uncles
and get their reward share anyway. Maybe Ittay Eyal and Emin Gun Sirer
can say more about this...

Best regards, Sergio.

--
Is your legacy SCM system holding you back? Join Perforce May 7 to find out:
• 3 signs your SCM is hindering your productivity
• Requirements for releasing software faster
• Expert tips and advice for migrating your SCM now
http://p.sf.net/sfu/perforce
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

Re: [Bitcoin-development] Bug with handing of OP_RETURN?

[Sergio Lerner]

El 03/05/2014 03:55 p.m., Mark Friedenbach escribió:
>
> On 05/03/2014 11:39 AM, Peter Todd wrote:
>> The standard format ended up being exactly:
>>
>> OP_RETURN <0 to 40-byte PUSHDATA>
>>
Please remember that the code actually does not implement the "standard
format" (at least the last time I checked it).  Any opcode after
OP_RETURN is accepted:

For example: OP_RETURN OP_CHECKSIG

is accepted.



--
"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos.  Get 
unparalleled scalability from the best Selenium testing platform available.
Simple to use. Nothing to install. Get started now for free."
http://p.sf.net/sfu/SauceLabs
___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development

[Bitcoin-development] Block collision resolution using the DECOR protocol and Bonneau's Kickbacks problem

[Sergio Lerner]

The Bonneau's Kickbacks problem is interesting because it is a
destabilizing incentive.
Just by luck yesterday I was working on the same problem. I found a way
to prevent Kickbacks and provide a conflict resolution strategy that
benefits all member of the network.
I will repost my blog post here, but the original has very nice diagrams
and is full of hyperlinnk, so I recommend you see the original post...

Even faster block-chains with DECOR protocol

One of the most interesting papers ever written about the Bitcoin
block-chain design is “Accelerating Bitcoin’s Transaction Processing” by
Sompolinsky and Zohar. The paper presents the GHOST protocol which aims
to achieve higher TPS securely by changing the way nodes decide which is
the best chain fork. One of the issues that is not considered by the
paper is the existence of a selfish bias independent of the miner’s
hashing power. When a miner solves a block, and a competing block is
also received, the miner will mine on top of his own solved block. This
is not only a consequence of the best-chain selection policy, there is a
strong incentive to do so. By mining on top of your own solved block,
you double the expected reward while keeping the same winning
probabilities. As a informal comparison, in Satoshi’s security model,
the rogue miner is irrational and malicious. For example, the
confirmation interval computations assume a rogue miner having 10% of
the network hashing power will try to mine a selfish chain in order to
try to outperform the global best-chain even if the odds are against
him. In Sopolinky/Zohar security model, the miners are rational, but use
a sub-optimal strategy. For example when two blocks compete, all miners
will chose one of them arbitrarily (all choose the same block). Although
this may be optimal for a fully cooperative network it’s not what miners
will optimally choose for themselves. In Eyal/Sirer security model, the
rogue miner is rational and uses an strategy believed by the authors to
be optimal.
In this post we improve Sopolinky/Zohar model assuming the attacker uses
Eyal/Sirer selfish strategy and the standard double-betting strategy.

Double-betting Strategy by Default

The double-betting is a mining strategy pre-programmed in the in Satoshi
reference miner. When a miner mines a block and a competing block is
also detected, the miner won’t switch to the other chain because is has
the same length, so mining will continue on the “selfish” fork. Of
course there is nothing inherently selfish with this strategy since the
miner has not enough information about which of the two forks is the one
which the majority of the miners are mining on top of. Nevertheless the
division of hashing power in forks is against the common good and
reduces both the network TPS and the network confirmation time.

Tit for Tat and identities

If the two competing miners could detect the other miners identity in
blocks, they could apply a cooperative strategy like Tit for Tat.
Whenever two competing blocks are found by two miners without having any
previous interaction, the conflict is resolved by both miners mining on
top of the block with lower hash digest. If the two miners have
interacted before, the conflict is resolved by both miners mining in the
block that was solved by the opposite miner chosen in the previous
interaction. If a miner acts selfishness and breaks the ties, then the
other miner opts to apply an equivalent retaliation in the next block
conflict. The retaliation is only considered successful if the miner who
retaliates wins the ties. This strategy may in practice for at least
four reasons:

Sometimes a miner may solve two blocks in a row without noticing that
the first one had a conflicting sibling. Then the competing miner would
retaliate.
If more than two miners are competing, it’s more complex to decide which
block should be chosen as parent.
All miners must dynamically maintain information of all previous
interactions between all other miners.
Some miners want to preserve anonymity and won’t publish identifying
information.

The first two reasons can be disregarded since the conflicting events
may have a very low probability. The third is only a minor technical
difficulty. But the last reason may be very strong.

DECOR (DEterministic COnflict Resolution)

I present here a reward strategy I called DECOR that incentives
resolving conflicts in a deterministic way that benefits all conflicting
miners at the same time. This strategy practically eliminates any
possibly block-chain reversal when miners are rational. To make this
explanation clearer we’ll assume that all block rewards and fees are
equal so each miner receives exactly the same net payment for a block.
Also the reward percentages proposed can be varied as long as some
relations between are maintained. The idea is that whenever two miners
Alice and Bob mine two competing blocks (a block conflict) both decide
to mine on top of the block with the lower hash. First, all conf

Re: [Bitcoin-development] Block collision resolution using the DECOR protocol and Bonneau's Kickbacks problem

[Sergio Lerner]

The original post is here: http://bitslog.wordpress.com/2014/05/02/decor/

--
"Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE
Instantly run your Selenium tests across 300+ browser/OS combos.  Get 
unparalleled scalability from the best Selenium testing platform available.
Simple to use. Nothing to install. Get started now for free."
http://p.sf.net/sfu/SauceLabs
___
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]

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.

---

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.

 

--
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?




--
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

[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.

--
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

[Bitcoin-development] SmartSPV – A better Simplified Payment Verification for Smartphones

[Sergio Lerner]

In a previous e-mail Mike Hearn asked me how I was going to handle 17K
block headers a day in my NimbleCoin currency in a the SPV mode.
I designed a variation of the standard headers-only SPV mode I called
SmartSPV. This mode could also be implemented by BitcoinJ for Bitcoin.

The method is explained here:
http://bitslog.wordpress.com/2014/04/25/smartspv-a-better-simplified-payment-verification-for-smartphones/

But I copy the whole blog post in this e-mail so you don't need to click
on it.


SmartSPV – A better Simplified Payment Verification for Smartphones

NimbleCoin  is a new cryptocurrency I’ll be
hopefully launching soon. One of its nice features is that it uses the
FastBlock5
 protocol
(a 5 seconds block interval) to achieve near instant payments. Because
NimbleCoin also implements merged mining
, each
block header can be as large as 700 bytes (including Merkle branch and
coinbase transaction). Yesterday Mike Hearn asked my a difficult
question: how would NimbleCoin SPV nodes (such as the ones running on
smartphones) process tons of headers if the bandwidth is limited or the
clients are disconnected from the Internet for long periods?

The answer is Smart-SPV, a variation of the standard SPV headers-only
 mode that allows a
smartphone to keep a fairly accurate state of the wallet balance without
downloading all the missing headers and without sacrificing battery life
and time.

Headers-only SPV clients

downloads a complete copy of the headers for all blocks in the entire
blockchain but not all the transactions. In order to update the user
wallet, SPV clients ask their peers to filter those blocks that contains
transactions that the SPV is interested in, such as those that have
payments to their own bitcoin addresses. This is done using bloom
filters .

In Smart-SPV mode, when a client is missing block headers two things
happen simultaneously:

1. The client starts downloading block headers from the last one solved
backwards.

2. The client starts downloading the blocks headers from the first
missing header, forward.

While the client catches up with all the missing blocks, the wallet
balance may not be fully reliable. Nevertheless if a new payment is
received and confirmed, or a new payment is made, the wallet will
increased the balance and show it. This is what the user expects.

*How it works*

A live block is a block which is the last block of the block-chain and
it’s received on time (it has a time-stamp near the current time). Each
time a live block is received, it is flagged as LIVE and this flag is
stored permanently with the block.  A live transaction is a transaction
that is included in a live block. When a live transaction is confirmed
by 6 blocks flagged as LIVE the transaction is considered mature. A
mature transaction may be included in a block that is still orphan. All
mature transactions are scanned and used to compute the balance of the
wallet. Also all transactions that are included in blocks rooted at the
last checkpoint and finishing in the last live block are also considered
mature (this is the standard condition). Since the wallet always
modifies the balance according to mature transactions, an payment is
received and acknowledged even if the branch where it is included is
still orphaned. If the SPV client clock is correctly synchronized, the
Smart-SPV protocol does not pose any additional security risk different
from the known SPV limitations.






--
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] Coinbase reallocation to discourage Finney attacks

[Sergio Lerner]

On 23/04/2014 05:51 p.m., Mike Hearn wrote:
> On Wed, Apr 23, 2014 at 10:44 PM, Adam Ritter  > wrote:
>
> Isn't a faster blockchain for transactions (maybe as a sidechain)
> solving the problem? If there would be a safe way for
> 0-confirmation transactions, the Bitcoin blockchain wouldn't even
> be needed.
>
>
> The 10 minute average comes from a desire to balance wasted work due
> to natural chain splits with latency. With a very fast block interval
> you end up with lots of forks and things take longer to converge,
> also, it can make attacks easier because an attacker is building on
> his own blocks so he doesn't suffer propagation delays and the
> attendant splits.
>
> It's not clear you can just make a faster block chain. 10 minutes is
> somewhat arbitrary, it could be 5 minutes and the system would still
> work, but it probably can't be 5 seconds.
5 seconds block interval is possible. I've simulate it with great
success and I encourage anyone to repeat or check my simulations.

There are a very few protocol modifications that are required to allow 5
seconds block, and most of them have already been discussed in the forums.
For more information you can check my post:
http://bitslog.wordpress.com/2014/02/17/5-sec-block-interval/
Also NimbleCoin is a new alt-coin that uses 5-sec block intervals,
allows 100 tps and  it's based on BitcoinJ (NimbleCoinJ now). So not
only it is possible, but it was coded by Mike itself.
Important note: the 5-sec block interval method probably requires a
block reward forever. It doesn't work well if there is no block reward
at all.

>
> Unfortunately for best physical-world usability you really need very
> fast payments. A few seconds is competitive with modern credit cards.
Another solution to achieve <5 secs block intervals is this:
http://bitslog.wordpress.com/2014/03/20/mincen-a-new-protocol-to-achieve-instant-payments/

So the problem with 0-confirmations is solely of Bitcoin and other
alt-coins, new alt-coins may achieve instant transactions and no not
have to rely on 0-confirmations.

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] Coinbase reallocation to discourage Finney attacks]

[Sergio Lerner]

(this e-mail is cc to the bitcoin-research list)

Hi everyone from the bitcoin-development mailing list!
I decided to join this legendary list because it seems that all the
research fun is taking place in here, and I don't want to miss the
research party.

Regarding the discussion about BitUndo, a year ago I posted about an
attack (which I called the the Bitcoin Eternal Choice for the Dark Side
Attack or ECDSA)
that tries to erode the confidence in Bitcoin by offering double-spends
as a service.

I think it's related to the last post from Peter Todd about the problems
with BitUndo.

Here is the link if anyone is interested in reading about it...
http://bitslog.wordpress.com/2013/06/26/the-bitcoin-eternal-choice-for-the-dark-side-attack-ecdsa/

Sergio D. Lerner.



On 23/04/2014 12:29 p.m., Peter Todd wrote:
> Interesting discussion re: incentive compatibility happening on the
> bitcoin-development email list:
>
> - Forwarded message from Mike Hearn  -
>
> Date: Wed, 23 Apr 2014 09:55:30 +0200
> From: Mike Hearn 
> To: Bitcoin Dev 
> Subject: [Bitcoin-development] Coinbase reallocation to discourage Finney 
> attacks
>
> Lately someone launched Finney attacks as a service (BitUndo). As a
> reminder for newcomers, Finney attacks are where a miner secretly works on
> a block containing a double spend. When they eventually find a block, they
> run to the merchant and pay, then broadcast the block. In a simpler variant
> of this attack you make purchases as normal with a modified wallet that
> always submits a double spend to the service, and then N% of the time where
> N is the percentage of overall hash power the dishonest miners have, you
> get your money back minus their fee.
>
> N does not need to be very high to render Bitcoin much less useful. Real
> time transactions are very important. Although I never expected it when I
> first started using Bitcoin, nowadays most of my purchases with it are for
> food and drink. If Bitcoin could not support such purchases, I would use it
> much less.
> Even with their woeful security many merchants see <1-2% credit card
> chargeback rates, and chargebacks can be disputed. In fact merchants win
> about 40% of chargeback disputes. So if N was only, say, 5%, and there was
> a large enough population of users who were systematically trying to
> defraud merchants, we'd already be having worse security than magstripe
> credit cards. EMV transactions have loss rates in the noise, so for
> merchants who take those Bitcoin would be dramatically less secure.
>
> The idea of discouraging blocks that perform Finney attacks by having
> honest miners refuse to build on them has been proposed. But it has a
> couple of problems:
>
>1. It's hard to automatically detect Finney attacks. Looking for blocks
>that contain unseen transactions that override the mempool doesn't work -
>the dishonest users could broadcast all their double spends once a Finney
>block was found and then broadcast the block immediately afterwards, thus
>making the block look like any other would in the presence of double 
> spends.
>
>2. If they could be automatically identified, it possibly could be
>converted into a DoS on the network by broadcasting double spends in such a
>way that the system races, and every miner produces a block that looks like
>a Finney attack to some of the others. The chain would stop advancing.
>
>3. Miners who want to vote "no" on a block take a big risk, they could
>be on the losing side of the fork and end up wasting their work.
>
> We can resolve these problems with a couple of tweaks:
>
>1. Dishonest blocks can be identified out of band, by having honest
>miners submit double spends against themselves to the service anonymously
>using a separate tool. When their own double spend appears they know the
>block is bad.
>
>2. Miners can vote to reallocate the coinbase value of bad blocks before
>they mature. If a majority of blocks leading up to maturity vote for
>reallocation, the value goes into a pot that subsequent blocks are allowed
>to claim for themselves. Thus there is no risk to voting "no" on a block,
>the work done by the Finney attacker is not wasted, and users do not have
>to suffer through huge reorgs.
>
> This may seem a radical suggestion, but I think it's much less radical than
> some of the others being thrown around.
>
> The above approach works as long as the majority of hashpower is honest,
> defined to mean, working to stop double spending. This is the same security
> property as described in the white paper, thus this introduces no new
> security assumptions. Note that assuming *all* miners are dishonest and are
> willing to double spend automatically resolves the Bitcoin experiment as a
> failure, because that would invalidate the entire theory upon which the
> system is built. That doesn't mean the assumption is wrong! It may be that
> an entirely unregulated market for