In another thread people are discussing the problems with unauditable implementations of ECDSA (https://bitcointalk.org/index.php?topic=883793.0). Everyone assumes a non-interactive signing method. If you allow interaction, then the solution seems to be easy.

A year ago, when I designed the Firmcoin (Firmcoin.com), I proposed an implementation of a ECDSA signer which uses a random k, but uses a fair coin-flipping kind of protocol to create a k that is private but auditable. In other words, the device and the software in the PC cooperate to create a k value that such that the following properties hold :

1. k is uniformly random and covert-channel-free if the PC software is not backdoored and the device is backdoored
2. k is is uniformly random and covert-channel-free if the PC software is backdoored and the device is not backdoored
3. The PC software cannot obtain the private key.

The full protocol is described here: http://firmcoin.com/?p=52

But I'm copying it here:

The signing of a transaction using the private key is a special two-party protocol. A ECDSA signature consist of the tuple (r,s). All known subliminal channels in ECDSA consist of hiding some information in r. s is computed deterministically from d_A, z and r (except from a single bit, which is the sign of y_1). Our protocol guarantees that r is indeed random.

This is the standard ECDSA signing protocol:

1. The signer calculates e = HASH(m), where HASH is a cryptographic hash function, such as SHA-1.
2. Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.
3. The signer selects a random integer k from [1, n-1].
4. The signer calculates the curve point (x_1, y_1) = k * G.
5. The signer calculates r = x_1 (mod n). If r = 0, go back to step 3.
6. The signer calculates s = k^{-1}(z + r d_A) (mod n). If s = 0, go back to step 3.
7. The signature is the pair (r, s) which is sent to the user.

This is our protocol (the user is the PC software the user trusts)

1-2. These steps are similar to the standard protocol.
3. The signer selects a random integer u from [1, n-1].
3.1. The signer calculates Q=u * G.
3.2. The signer calculates h=HASH(Q). This is a commitment to Q.
3.3. The signer sends h to the user.
3.4. The user selects a random integer t from [1, n-1].
3.5. The user sends t to the signer.
3.6. The signer verifies t is  [1, n-1]. The signer sends Q to the user.
3.7. The user verifies that HASH(Q)=h. If not equal, then the signer is cheating.
3.8. The signer calculates k = t * u.
4-7. These steps are similar as the standard protocol.
8. The user calculates the curve point (x_2, y_2) = t * Q.
9. The user verifies that r = x_2 (mod n). If not equal, then the signer is cheating.

This protocol guarantees that the r value is chosen uniformly random from the set of x-coordinates of curve points, and at the same time guarantees that the user cannot arbitrarily force this value.
It must be noted that the protocol should not be repeated unlimited times if it fails. If failure occurs after step 3.5, and not before step 6, because of the signer not responding properly (either providing and invalid message or by not responding at all), then a new iteration of the protocol may allow the signer to leak some information. If the signer fails n times before finishing the protocol properly, then a side channel that hides approximately log2(n) bits may have been tried. For an 256-bit ECDSA private key, we would not recommend executing the protocol more than 16 times if is continuously fails, limiting the amount of information leakage to 4 private bits.

If you find a vulnerability with this protocol please let me know. Also if anyone wants to do a formal analysis of it that would be awesome. As far as I have studied it, it relies on the same crypto assumptions of ECDSA.

Best regards,
 Sergio.

If you're honest and you're really storing the blockchain, it takes less resources (CPU/bandwidth) to compute a response to the proof-of-unique-copy challenge-response protocol than to send 10 random blocks asked via "getblocks". So providing this protocol does not increase the DoS risk.

Anyway, it's just an new idea. It's not something to rush to add to Bitcoin.

In the thread https://bitcointalk.org/index.php?topic=310323.0 people are discussing how to prove to a peer that one has invested some expensive resource. I was researching on a topic that has some common applications that I think can be useful in cryptocurrencies.

How to prove that one have an unique copy of the blockchain?

This is important for several reasons:

1. It allows anyone to scan the network and check its health, measured by the number of distinct copies of the blockchain in existence.
2. It allows to give higher priority to peers which store the full blockchain (and penalize SPV).
3. It allows to establish a minimum resource consumption to prevent distributed DoS attacks.

The article is on my blog: http://bitslog.wordpress.com/2014/11/03/proof-of-local-blockchain-storage/

The core idea is to use asymmetric-time functions to store the blockchain in a transformed state (by applying f, which is slow), where the transformation depends on the peer IP address. The data is recovered by applying the inverse of f (which is fast).

I've run simulations to check AttackerSuccessProbability, just to be sure, and I don't get the same results.
It true that when q approaches 0.5, p approaches 1, but the exact numbers differ.

In my simulations, the catchup probability for a 1 block deficit for an attacker having 30% of the network hashing power is approximately 0.43.

Catchup probability:  0.43
Avg Catchup Time : 24.71 minutes (when it catches up)

Assumptions:

Honest rate: 0.0011666666667 =1/(10*10/7*60) (70%, one block every 14.2 minutes on average)
Attacker rate: 0.0005 = =1/(10*10/3*60) (30%, one block every 33.3 minutes on average)

Event time function:


The probability of catchup when a single block is mined (by either the honest branch or the attacker) is about 0.30.
That is counting the cases where nextTime(attackRate)<nextTime(HonestRate)

Code:
(As you've noted, it's written in Turbo Pascal 6.0 )

It's probable that my simulation has some kind of flaw or the rates are not set properly.
Have anyone run simulations to check Satoshi formulas?

So the problem with my interpretation is that I was not considering that the attacker could catchup after an infinite number of steps/time...

After some time I gave the Satoshi paper a second read.
I executed the AttackerSuccessProbability() code and computed AttackerSuccessProbability(0.3,1)
(Greg has an online tool to do that here: http://people.xiph.org/~greg/attack_success.html)

The result is 0.627749

Maybe I misunderstood the paper, but this seems to imply that an attacker having 30% of the network hashing can catchup after a 1 block deficit with probability 0.62.
Either this interpretation is incorrect or something in the Satoshi formulae is wrong: an attacker having less than 50% of the hashing power cannot have higher than 50% probability of catching up! That's counterintuitive.

If he had, then the most probably outcome would be that the attacker catches up (in some number of steps).  Since the good branch has more than the double of the attacker hashing power (70% vs 30%) the most probable outcome for the first step is obviously that the good branch mines another block, and not the opposite. So the most probable outcome is that the deficit is increased.

Can anybody clarify this to me?

Hi Cashmen!
 I received the inquiry to do the security Audit in the Coinspect contact form. I will respond to the e-mail given.

I've audited BitShares, Counterparty, NimbleCoin, currently auditing Ethereum and Coinspect is also auditing a cryptonote derived crytpcurrency.
And of course I've audited Bitcoin, but for free.

I will a pleasure for me to audit Cloakcoin if you choose me. I really like what I do.

Best regards,
 Sergio.

 

Thank you very much Luke.

I've setup a local stratum server using eloipool. I'm trying to test the stratum server manually using either telnet or curl as in:

curl --data-binary '{"id": 1, "method": "mining.subscribe", "params": []}'  -H 'content-type:text/plain;' http://myuser:mypassword@127.0.0.1:3334/

The connection is closed as soon as the first line of the http headers is sent (usually POST) (curl prints: curl: (52) Empty reply from server)

Any idea of what's happening?

I hope you find a solution without involving crypto, but I doubt that solution exists. I worked on the subject for a couple of years in 2009.

I'm currently working with 4 other people around the globe to bring MPF into practice. We improved the original protocol and we can deal cards in seconds with cryptographic security and without bloating the block-chain. We can recover from players dropping out without problem. We can handle time-outs, time-banks, and tournaments.

I don't know yet if the platform will be called QixCoin (as the original) or not, but I can say that it will be launched in 1Q of 2015 (that's our plan)

Best regards and I hope you come to play in it when it's ready.

Sergio Lerner.

My best guess is that Satoshi preferred the input/output model because it makes very easy preventing transaction spam on the network (before inclusion into the blockchain).

When you adopt the account/balance model, you must choose one of the following design decisions to be able to detect double-spends (which can be used to DoS the network):

1. Require transactions to include a proof-of-work
2. Predict the balance of each account every time you receive a transaction
3. Reduce the block interval to a value so small that allowing a single transaction per block is enough for the user (e.g. 5 seconds). Then you forward a single transaction per account between blocks.

There are surely more solutions, but probably more complicated.

The simplest solution (for a 10 minute block interval) is the one Satoshi choose, because it does not require additional temporary data structures.

Sergio.

Somebody asked for some other ways for anonymization: you can check my old paper on AppeCoin at
https://bitslog.wordpress.com/2014/04/24/appecoin-anonymous-cryptocurrency-draft/

It uses universal encryption, so everyone can mix every other peoples outputs without asking for permission, and it's impossible for dishonest mixers to prevent honest mixers from mixing with high anonymity set (at least of course if 99.9% of the outputs in the blockchain are controlled by the attacker).

I'm creating a patch for a bug in bitcoind code, and I'm compiling bitcoind on a Ubuntu virtual machine with 1 GB of RAM and 1 core.

What can I do to speed up compilation?
Will adding an additional core decrease compilation time? Does it benefit from "make -j 2"?
Will adding more RAM decrease it?

Best regards,
 Sergio.

This is my plan:
 
When NimbleCoin is ready, we test it thoughtfully. If you want to donate to the NimbleCoin project, I would happily use the money to hire another programmer and finish it faster. I'm trying that NimbleCoin does not have pre-mining because I don't like pre-selling coins. If NimbleCoin succeeds, then we can implement every feature back on Bitcoin with a hardfork. If it fails, then we still have the open source code to experiment with.

NimbleCoin is implemented on Bitcoinj, so we'll have a known reference code to play with.

Best regards,
 Sergio.

I will give you my opinions on gmaxwell points of views. My opinion is backed up with several simulations and successfully lowering the block interval  to 5 seconds, and a cryptocurrency (Nimblecoin.org) that works with 5 seconds interval:


True, but transactions can be and are  in practice pre-verified by nodes, so validation delay is zero.  Communication time can also decrease considerably using header-only block propagation. Using DECOR+GHOST protocols you remove selfish mining incentive and increase best-chain choice  convergence.

The limit where things start to fail is using a block interval of about 2 seconds.


100% true, but they were not using DECOR+GHOST protocols

Half true, because SPV security is terribly weak anyway: it requires trust in peers and most implementations of SPV rely in a single trusted node.
I prefer SmartSPV security, which does not need to download all headers.
But I would also prefer to trust a single US company to send me each block to my smartphone (such as coinbase) than to trust a random Bitcoin node.
Anyway, I suppose that an increase in 5X in the number of headers is completely tolerable to almost any SPV node.


Not really, the most important factor is the number of confirmations, and not the accumulated work. So a DECOR+GHOST alt-coin with 1 minute interval takes 10 times less than Bitcoin to confirm with the same security.


A 4-block confirmation in Nimblecoin.org (about 20 seconds) has a 0.1% reversal probability.
In the current p2pool you would need 1000 shares to achieve the same level of confidence or 8 hours.
A better p2pool could be created where each better-p2pool share must include all the previous share transactions. For this better-p2pool to achieve the same with shares, you would need 4 new-p2pool blocks (about 2 minutes) to have the same guarantee.
But taking into account that p2pool only has a small share of the total hashing power, you cannot expect secure confirmations from p2pool.


With a 5-seconds block epoch, and 4 confirmations, the described bad case (which happens once per week probably) would take less than two minutes. Pretty good for any application to have 2 minutes delay once a week.

It's true, but Bitcoin may have to face competition in the future. I think that a really compelling argument will be when other alt-coins achieve 1000 tps and 10 seconds average confirmation and Bitcoin won't. Bitcoin probably cannot go down to 5 seconds but it can surely go down to 30 seconds.

Best regards, Sergio.

There is a fourth possibility, which I'm trying to achieve with NimbleCoin.org:

d) Other alt-coin using Bitcoin merged mining emerges that provides Bitcoin miners the additional incentive to secure both networks with the same investment and double their earnings so that fees don't have to rise.

It may sound a little pretentious, but I think it can be done and hope I'll do it right. I'm betting all my technology into NimbleCoin.org: instant payments, full scripting language, 100 tps ready from day 0, scalable to infinite tps without requiring protocol modifications. The revenue model of NimbleCoin is not based on pre-mining but in donations to pay for development. I have the white-paper 1.0 ready and I've be publishing soon...

Taras, block 286 may not be Satoshi's. Please be careful with easy conclusions.

Here is a possible mining pattern of another miner that pass through block 286.



Many blocks with a low extraNonce can be confused easily with Satoshi's because most other miners start and stop mining with low extraNonce values, and have very few blocks in their pattern.

Yes, it was my mistake. Thank you Andrew for clarifying this to me.

For weakly Nonoutsourceable Puzzles was true but for strongly Nonoutsourceable Puzzles the pool admin can only get a clue of who might be a cheater but no real evidence.
Nevertheless the clue may be strong (for example, if the supposedly cheating miner that is member of the pool has 0.1% of the total hashing power, the probability that this miner has not cheated is 1/600000) .

Here is my post I published today about this topic.. I hope it adds some new issues to be discussed...
(http://bitslog.wordpress.com/2014/06/19/theoretical-and-practical-nonoutsourceable-puzzles/)

Theoretical and Practical Nonoutsourceable Puzzles

The idea of a theoretical non-outsourceable puzzle is very tempting, and I encourage anyone to read the paper and try their constructions. Nevertheless I see four problems with this approach. Two are theoretical, one is legal and the last is practical. The core idea of the paper is that if if a miner can steal a block from the pool admin, and the pool admin has no way to catch the stealer, then there is no incentive to become a pool admin, since no solved blocks will be shared with the other pool members.

Problem 1: Mining cartels

If at any time 51% of the miners decide to prevent the others from mining solo, they can stop mining on top of the blocks they solve or they can blacklist their coinbase addresses.  Then all miners would be forced to join pools and include in each block (as a transaction or in any other part) an identification of the mining pool they belong. Then a Nash equilibrium arises: miners cannot mine solo (unregistered) because pools won’t mine on top of unregistered blocks so they will join pools, which re-enforces the disincentive to do solo mining because of they blacklist solo blocks.

Problem 2: Finding a cheater can be easy, even with ZNPs

Suppose a miner (called a “server” in the paper) wants to steal a block from the pool admin (called a “client” in the paper). First we must make clear that both the miner and the pool admin want to collaborate in a pool. They will do whatever is necessary to achieve collaboration. So the pool admin can set rules to catch a stealer that miners agree to obey. With punishment rules, the miner admin can always punish a miner that tries to steal a block even with a  non-outsourceable puzzle. Suppose the pool admin forces each miner to scan a certain nonce space (so nonce is watermarked by as 128-bit secret key and must be incremented sequentially) while mining. Suppose also that the pool admin asks each miner to send the best share found every second to the pool admin (to be paid in accordance) along with the nonce used for that share, and checks that the nonce is in the expected range, according to the miner declared computing power. Since every miner obey, so far the pool works. But the pool admin can track which is the nonce being scanned by any miner at any time. Then, whenever the pool admin sees a stolen block being published, he just need to scan the nonce space of at most 1-second of each miner member of the pool to detect if the cheater is a miner from the pool (or a random number of seconds between 1 and 30).

Let’s see an example: Suppose that the pool hashing power is 10% of the total hashing power. Suppose that stolen blocks are unusual (say 1% of the time). Suppose that miners must send shares every second to the pool admin. Then the pool admin would only need to spend 1/600000 = 0,0016% of the pool hashing power in finding a cheater. The hardware used to find a cheater could be owned by the pool admin, or even the search could be conducted by the pool itself, giving a reward to the miner who finds the cheater. This will obviously take to the pool about 1 second of processing, if the cheater is part of the pool. So there is a trade-off between using the pool resources to find the cheater or using the pool resources to mine more blocks. Note that the pool admin does not need to look at the content of the block, not try check the presence of any watermark in the block. He just need to re-do the last 1 second work of the pool to check if the cheater was in the pool.

I suppose that there is a Nash equilibrium: if the stolen block rate is low, pool admins can detect cheaters and so nobody will be willing to try to steal, so the stolen block rate will be low. It needs all miner to rebel against the pool operators and steal all block in order to prevent the detection of cheaters.

Problem 3: Nonce Watermarks

Mining pool admins and members of the pool can agree to have their own block watermarked. A watermark can be embedded into a nonce like, for example, nonce(i) = HMAC(k,i) || i , where k is a unique secret symmetric key shared between each miner and the pool admin. Even if the nonce is hidden by a Zero-knowledge-proof, the pool admin can re-scan the nonce space and detect the watermark. The probability that the watermark is present by chance can be made arbitrarily low, such as 2^-128. So the watermark is a proof of the violation of tacit (but 100% legal) agreement between both the miner and the pool admin which states that the block reward belongs to the pool, and not to the miner. So the pool admin can go legally against the cheater. Nevertheless, going legally is only a good option if information regarding the identity of each pool member is collected by the pool admin.

Problem 4: Complexity

The constructions proposed by Miller are far more complex than the well-known Bitcoin SHA-2 PoW. More “esoteric” cryptography  (as Schneier used to call it) must be carefully analyzed and implemented without bugs.

 
A Practical and Simple Proposal: BlockPow

I will propose a kind of PoW puzzle that only practically prevents mining pools for certain cryptocurrency settings. The idea is that if miners try to join a pool, then they incur in overhead 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: BlockPoW

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.

I need to send a non-standard tx. Eligius's  192.3.11.20 seems to be off-line (at least not on port 8333).

Anybody knows a miner/miner pool that accepts non-standard txs right now? Is there another Eligius IP available?

Thanks, Sergio.