Quote from: arhag on July 07, 2015, 12:34:30 am

We just need our own version of Lightning network for micropayments.

If the Bitcoin Lightning network is feasible, and allows full scalability of Bitcoin, what does that mean for the strategic positioning of the bitShares network in the market? Are the two networks mutually exclusive, or can they interact to leverage their relative strengths in different applications?

The lightning network is only useful for transfers of funds between users (so it won't be useful for smart contracts and markets). And even then it is most beneficial if users tend to stick with one asset (e.g. BitUSD) and for smaller amounts (so it is perfect for microtransactions). Furthermore, because of the small block intervals and high TPS of BitShares, it allows the settlement period for the BitShares lightning network to be much smaller (we could handle everything settled once per day for everyone).

I'm not sure what you mean by the networks being mutually exclusive. And I don't see what Bitcoin's relative strength would be other than the fact that it (currently) has the stronger network effect.

Thanks.. the search through a lot of "trust" results

Let me give you a little trick on the best way to search for things on this forum:

https://www.google.com/search?q=site%3Abitsharestalk.org+rust

Quote from: arhag on July 03, 2015, 03:56:00 am

Is anyone actually working on this bounty?

I am, but at a very low pace.

Glad to hear someone is working on it. 

Bitccoin and nearly every other derivative (btishares included) uses an amortized consensus; the network of block producers gradually comes to an consensus on the transactions in a given block - they do this by building other blocks on top of the previous one, thereby adding a confirmation. This is why you need to wait for multiple confirmations before processing a transaction, because otherwise you only rely on the opinion of one entity, instead of the majority of the network.

Ripple, however, uses a non amortized (there is probably a better word) consensus, in that all the block signers actually work simultaneously on the current block in production. This means you get an entire network's worth of consensus on new transactions as soon as the block is produced.

DPOS could achieve the same thing if all witnesses sent their signature for the previous block to the next witness that is supposed to produce a block. That witness would collect all the signatures and include it in the block. If a large enough quorum (e.g. 80% to be consistent with Ripple) of active witnesses signed off on a particular block, then that is essentially the same thing as a ledger close in Ripple. This means in practice a block could usually be considered valid by a super majority of the active delegates in 2 seconds (two blocks with 1 second intervals).

If you want to avoid bloating each block with extra signatures from 80% of active witnesses you can use threshold signatures instead (as I have proposed here). You can increase the delay from 1 block to some other small number of blocks to give the witnesses enough time to coordinate the threshold signature generation. For example, instead of this threshold signature signing the previous block it could sign for the block that is 3 blocks in the past. In that case a block could be considered valid by a super majority of the active delegates in 5 seconds. However, for the threshold signature generation to be simple and fast, ECDSA and secp256k1 aren't going to cut it. We would need to use EdDSA which is a variant of Schnorr signature based on Twisted Edwards curve. The NaCl library seems to be a good implementation of this digital signature scheme for regular signatures, but it would need to be modified (see this paper for the cryptography necessary) to support threshold signature generation. Of course if that code was created and integrated into BitShares, many other users (particularly businesses who want to hide their authentication organizational structure from the public) could also take advantage of threshold signatures. Plus there are lots of other benefits to using EdDSA as well.

Is anyone actually working on this bounty? Here are my thoughts on how this bounty should be restructured.

I think wrapping the crypto primitives from secp256k1-zkp in a nice friendly C++ interface that we can use to intuitively do crypto math (adding/multiplying 256-bit numbers modulo order of the curve, adding curve points together, and multiplying a 256-bit scalar with a curve point, etc.) is a project of its own that could act as a prerequisite to this blinded signature project. It should also implement or wrap HMAC-SHA512 as that is needed for BIP32, which as far as I am aware libsecp256k1 does not implement but OpenSSL might. (By the way, why do we bother with a choice in the fc library between an OpenSSL implementation for the ECC math versus the libsecp256k1 one? At this point can't we just commit to the libsecp256k1 one? The secp256k1-zkp dependency is needed anyway for the Confidential Transaction stuff, right? It's also a bit frustrating seeing the public_key and private_key implementations depend on OpenSSL's bignum while libsecp256k1 apparently implements its own bignum stuff in order to do the ECC math.)

Then after that, those crypto primitives could be used to build extended_private_key and extended_public_key which can be used for proper BIP32 hierarchical deterministic wallets (honestly I was surprised to find out that wasn't already implemented in BitShares).

Then finally, the crypto primitives and extended_private_key/extended_public_key classes can all be used to implement Oleg's algorithm in a pretty straightforward and easy way. In fact at that point I would be interested in implementing my own modified version just to see how it works.

So I see this bounty broken down into those three separate projects. I think it would make this task more accessible for people. And in my opinion, the first one should be worth more than the second, and the second worth more than the third.

Mmmm brownies. This will be a fun experiment.

I appreciate whatever amount you think is fair (BTS handle: arhag). My contributions are just the public proposals, critiques, and analysis that I have shared on this forum (and a little on GitHub) over the past year now.

I have to say though, far more rewarding than any Brownie Points is seeing the ideas and changes I have fought for on this forum finally realized (in some form or other) in BitShares 2.0: generalized BitAssets, dynamic parameters, adding back TaPOS, separation of delegates and workers (this one was such a struggle for some reason), only enforcing maintenance collateral limits & allowing collateral to be adjusted up and down (see the two paragraphs after the third quote), and proper limit orders instead of WYAIWYG. Now just give us child DACs (I can see you guys might have already discussed some initial ideas similar to this from this doc), blockchain pruning & better light client security, and dividends (unfortunately dividends become either very complicated or impossible with Confidential Transactions, and so does seizing funds for that matter), and I'll appreciate that far more than any amount of BROWNIE.PTS.

BitAssets directly or indirectly using UIAs as collateral (actual UIAs not just privatized BitAssets) are not backed by BTS. All other BitAssets are ultimately backed by BTS though. An example of a BitAsset backed by a UIA could be a BitBTC backed by a SOMEBANK.USD UIA (which is an IOU for SOMEBANK's dollars). Another example could be a BitUSD backed by BTCIOU UIA where BTCIOU is redeemable for BTC by some multisig group that is holding the BTC reserves on the Bitcoin blockchain. A poor example would be BitBTC backed by BTCIOU or BitUSD backed by SOMEBANK.USD, because in those situations it makes absolutely no sense to hold the BitAsset when you could accomplish the same goal by just holding the collateral UIA with less overall risk.

The disadvantage of having a BitAsset backed by a UIA is that you are exposed to counterparty risk with respect to the entity that is backing the value of the UIA (the UIA issuer). On the other hand, despite the added counterparty risk, the value of that UIA might be less volatile relative to the asset to which the BitAsset is pegged compared to BTS, which might reduce black swan risk. So I guess in those situations you have to ask yourself which is more risky: the reserves of the UIA issuer being stolen/compromised/hacked/seized/mismanaged or the market price of BTS dropping significantly (like more than 50%) in a very short period of time.

Here is my attempt at modifying the protocol to fix the unsolicited sending problem. I am not sure if this change doesn't break the security (Yes it does! See Edit2) or privacy guarantees of the original protocol. I highly appreciate review of this modified protocol.

There are three parties involved: Alice, Bob, and Carol. Bob is designated as Alice's blinded signer publicly in her account metadata. Carol wants to send funds to Alice without needing any private data from Alice. Carol knows she is sending the funds to Alice, so there is no point in blinding Alice's withdraw signature from Carol. The protocol however needs to guarantee that Carol does not have enough information to get Bob to sign a digest that allows Carol to reclaim the sent funds. Bob only needs to verify that a particular user requesting him to generate a blinded signature is a customer (and verify their identity through whatever means is appropriate to provide the multisig protection) before signing with the appropriate keys meant only for that customer. No one other than Alice or Carol (this includes Bob) should be able to associate the sent balance to Alice at any time in this process including after Alice withdraws the balance using the unblinded signature.

Alice's extended public key is K_a (and corresponding private key is k_a). Bob's extended public key is K_b (and corresponding private key is k_b which is specific to Alice.

Carol generates a one-time private key o (corresponding public key is O). She generates shared secret s from the x-coordinate of o * K_a (which can also be derived by Alice using O * k_a). The modified shared secret s' = H (s || "modified"). The index i = H(s' || "index1"), a second index j = H(s' || "index2"), and the values v₁ = H(s' || "value1") and v₂ = H(s' || "value2"). Comparing to the paper, v₁ == a^-1c^-1 and v₂ == d. Carol also uses index i to derive the child public keys P (represents the same P as the one in the paper) and Q', where P = ND(K_b, 2*i + 0) and Q' = ND(K_b, 2*i + 1). She also uses index j to derive the child public key B' = ND(K_a, j). Comparing to the paper, Q' = a^-1Q and B' = a^-1bG.

Carol then calculates kG = v₁P (from the paper, kG == a^-1c^-1P), and r which is defined to be the x-coordinate of kG. From the paper, T (the public key in the withdraw condition) is given by T = r^-1(a^-1bG + a^-1Q + a^-1c^-1dP). We can rewrite this as T = r^-1(B' + Q' + v₁v₂P), which Carol is able to compute.

When Alice receives the funds she can verify that Carol followed the correct procedure. She is able to generate all the same values (including r) starting from the shared secret s. When Alice finally wants to withdraw the funds in another transaction she is going to need the values for a, b, c, and d. Through the index j she is able to calculate the private key for B', which is equivalent to a^-1b from the paper (call that value v₃). By selecting a random value for a, Alice can then calculate the remaining values: b = av₃, c = a^-1(v₁)^-1, and d = v₂. This then allows Alice to generate the blinded digest of digest h: h₂ = ah + b. However, Alice cannot only send h₂ and i to Bob, she must also send a to Bob. As far as I am able to tell, this should not reveal any new information to Bob (would really appreciate a check on this). Also with knowledge of a, even if Bob is colluding with Carol, they cannot withdraw the funds because they are unable to derive b (Not true! See Edit2). However, if Bob and Carol are colluding, Carol can share j with Bob which along with a and h₂ allows Bob to associate h₂ (and thus Alice's identity) to the digest h (and thus to the balance that Carol sent Alice). But if Bob and Carol are colluding anyway, Carol could just simply tell Bob this information as she was the one who sent the funds to Alice in the first place.

Bob now takes h₂, i and a provided by Alice and computes p^-1 (where P == p^-1G) and q' (where Q' == q'G == a^-1Q == a^-1qp^-1G). Then he computers q = apq'. Finally, Bob computes s₁ = ph₂ + q, sends s₁ back to Alice.

Alice can then use s₁ to compute s₂ = cs₁ + d. The unblinded signature on digest h is then (r, s₂) which is signed using a key corresponding to public key T. This signature allows Alice to withdraw her funds.

Edit: Require Bob's extended public key to be a hardened child specific to Alice or else Alice could determine Bob's master private key by getting him to blinded sign the same hash but with different indices. Even if the private keys for P and Q' were uncorrelated, the master private key could have still been computed by getting him to blind sign the same hash four times but with different indices. This also removes the requirement for Bob to track indices for which he has signed before.

Edit2: Major flaw found with the above. If Bob and Carol are colluding, they can determine k_a after Alice signs the transaction that withdraw funds sent by Carol. s₂ = c*p*a*h + c*p*a*(k_a + j) + c*p*a*q' + d.  Carol knows a*c, d, and j. Bob knows p and q'. Together they know y₁ and y₂ where s₂ = y₁*(h + k_a) + y₂. After Alice publishes the transaction to the network to withdraw the funds, she also necessarily publishes h and s₂, and so at that point Bob and Carol can simply solve for Alice's private key k_a. Back to the drawing board I guess.