Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove PoW requirement on RECEIVE tx #464

Closed
triwebb1 opened this issue Jan 9, 2018 · 21 comments
Closed

Remove PoW requirement on RECEIVE tx #464

triwebb1 opened this issue Jan 9, 2018 · 21 comments

Comments

@triwebb1
Copy link

triwebb1 commented Jan 9, 2018

Discussed in Issue 360

Requiring PoW on RECEIVE txs puts a large burden on services that accept XRB deposits, and if a user were spammed with penny-sends then it is difficult for them to clean it up.

Having a min PoW on RECEIVE txs makes it pretty efficient to identify and discard spam quickly, however it does not prevent spammers from broadcasting underworked RECEIVE txs. Because RECEIVE txs must match 1:1 with SEND txs there is no risk of ledger spam on the RECEIVE side. Only SEND can be the source of ledger spam. PoW does not prevent network spam.

Instead of using PoW as one of the first criteria to validate RECEIVE txs, a bloom filter can be used first to confirm that the SEND being claimed is still pending. The bloom filter will have to match for all pending SEND's. If the bloom filter check returns "this RECEIVE's SEND is definitely not still pending" then this spam RECEIVE is discarded. If the filter says it may still be pending then this spam check is passed.

There may be slightly better ways to implement this, or maybe it already is implemented, but the gist of it is that PoW on RECEIVE txs is hurting a whole lot more than it is helping so it should be disabled.

@slstuart
Copy link

slstuart commented Jan 9, 2018

Unfortunately, requiring PoW for receive is needed to prevent spam attacks. What you are essentially doing is sending out a message to your peers that says you receive a TX, and you are requesting that they broadcast to the network. The nodes essentially say "ok, I will broadcast this, but show me your PoW first". The idea is that all actions that consume network bandwidth via rebroadcasting need to have an associated PoW cost, otherwise spam attacks are possible. This way spam attack can DDoS particular node(s), but not the network.

@PlasmaPower
Copy link
Contributor

PlasmaPower commented Jan 9, 2018

Not really, if we double the PoW of a send, then the cost of your hypothetical attack stays the same (if we don't rebroadcast receives until we have the send).

@slact
Copy link
Contributor

slact commented Jan 9, 2018

a bloom filter can be used first to confirm that the SEND being claimed is still pending

This would require a counting bloom filter, which destroys CPU cache way faster than a regular bloom filter. Many random memory reads to n-bit integers, instead of random memory accesses to single-bitfields.

@slact
Copy link
Contributor

slact commented Jan 9, 2018

Another point is that Receives can be generated as-needed, and don't even need to be broadcast in-order. During a penny-spend spam attack on an account, the owner can choose to receive the largest sends first, working his way through the penny-send queue when idle.

@clemahieu
Copy link
Contributor

clemahieu commented Jan 10, 2018

I've thought a bit on this topic, one aspect is every receive requires a send which means each receive is explicitly linked to a single send transaction which already has PoW. Another aspect is the concept every time something is added to the ledger, a proof of work is verified which is more of a universal pay-to-play.

There is an important property with requiring PoW on each block and how it relates to forks:
If PoW is attached to each block, precomputing a sustained fork attack requires an exponential amount of PoW with respect to the depth of forked transactions. This is reasoned as follows:
If we have a head block H and we offline compute H1 and H2 which are successors to H and are forks with each other this requires 2 PoW computations. The network will reject H1 or H2 depending on the vote results but the attacker doesn't know which one will remain the new head block. Since now there are two possible head blocks, the attacker will need to compute 2 PoW per possible head block in order to sustain a fork attack.

This means to offline compute a fork attack of depth N we need 2^N precomputed blocks which also require PoW attached to them. If we remove PoW from any block it becomes significantly easier to make a very large precomputed attack.

@triwebb1
Copy link
Author

triwebb1 commented Jan 10, 2018

@slstuart - A node should not rebroadcast any tx which it does not know to be valid, and I'm proposing the use of an efficiently constructed bloom filter to use as a first line screening of RECEIVE txs instead of the PoW filter. If the RECEIVE fails this (hopefully) efficient first-line screening then it is dropped and not rebroadcasted, thereby preventing DDoS in the same way as the PoW filter.

@slact - Perhaps a counting bloom filter is not the best approach, perhaps a standard hash table or whatever memory structure is currently in use for looking up txs? Idk what the best approach would be, but surely there is a sufficiently efficient way to do this check. Yes, the target of a penny spend attack could create RECEIVE's for largest txs first, but that doesn't change the fact that it will be difficult for them to rake in all that dust. Not just for the purpose of increasing their balance, but also to get those SEND's out of 'pending' state so they can be pruned. The bigger issue with RECEIVE PoW is for services who might have 100k deposits in a day. If some XRB-based service takes off and millions of people start using it, that service might have to invest significantly in PoW infrastructure just to accept those payments if outsourcing the RECEIVE PoW isn't possible for their business. Typically distributions from these kinds of services happen in fewer txs with larger amounts in this model, so the burden of the SEND PoW may be 2 orders of magnitude lower than the RECEIVE PoW burden would be.

@clemahieu - That's an interesting point. I do not yet have deep knowledge about how RaiBlocks resolves forks, but I was under the impression that the voting mechanism would prevent any such pre-computed attack because the mere presence of a block in the local db is what decides the vote, not the length of chain after that block. If an attacker broadcasts H1 and H2 then the weighted depth of network propagation of H1 versus H2 is what will be the deciding factor in resolving the fork, not the length of chains or accumulated PoW. It is my understanding that the successors of H1 and H2 do not influence the vote at all, only H1 and H2 are considered because that is where the conflicting SEND's are, so an attacker has no reason to precompute more that 2 blocks. I'll have to dig deeper here, I've been curious about it anyway. It would be great if you, or someone else, could expound on the Wiki article to explain what "network propagation period" is, and explain how/why votes can be counted which result in a "no forks" conclusions, and if there is some sort of chain-work measurement factored in then explain that.


In thinking a little more about this proposal I've realized that the simple bloom filter I proposed is not enough. Currently when an underworked spam RECEIVE is being processed it can safely be discarded because of the low work. In my proposed system, if a spam RECEIVE comes in which fails the bloom filter check that could mean two things:

  1. The RECEIVE should be discarded because it is spam, meaning it is trying to claim an already claimed SEND, or trying to claim an invalid SEND, or it is a duplicate.

OR

  1. The RECEIVE is claiming a SEND that this node has not yet received from the network, so hold it until synced, and rebroadcast to other nodes if confirmed valid in the future.

There is no way to know if the SEND being claimed is invalid or just not yet received from the network.
This means that if the bloom filter check fails for this RECEIVE then the RECEIVE needs to be held in a buffer to await full network sync, and that could be a DoS attack vector.

The current PoW model surely has the same problem but the valid PoW basically 'buys' the space in the buffer so it's not a big deal. With no PoW it would be possible for a spammer to flood the waiting-for-sync RECEIVE buffer and severely disrupt that node's ability to sync with the network. Flood detection could be added (if it doesn't exist already) to rate-limit any node that is spamming unverifiable RECEIVE's, but relying on that is not as elegant as PoW.

Proposal:

  1. Remove PoW requirement from RECEIVE transactions.
  2. Add bloom filter or other efficient lookup so that the SEND being claimed by an incoming RECEIVE can be quickly validated.
  3. Add a queue for RECEIVE's which are claiming a SEND that this node does not have yet. I imagine this queue already exists. When queue is full the oldest RECEIVE should be pushed out. RECEIVE's that have been sitting in the queue for a long time should be flushed. RECEIVE should only be queued if all checks pass except for the SEND not being available. The claimed SEND id should not be malformed.
  4. Add accounting for peer messages, if it doesn't exist, and rate-limit RECEIVE messages from each peer if they send too many unverifiable RECEIVE's too quickly.

Benefits:

  1. Remove barrier to entry and reduce operating costs: Exchanges and high-volume XRB-accepting services will not need to invest in a GPU farm to accept XRB payments.
  2. Increase pruning potential: by removing the cost of committing SEND's. If an account does not need to spend XRB they may well let lots of SEND's just sit around rather than doing the work to commit them to the ledger. If it is free to commit them then there's no good reason to not do so, and after being committed the SEND's can be pruned.
  3. Penny-spend attack mitigation: If an account is ever intentionally or accidentally attacked with thousands or millions of penny-spends it becomes trivial to clean them up. Not cleaning them up adds bloat to the DB and makes that XRB unspendable by the owner. The burden of PoW is still carried by the sender.
  4. Minor wallet simplification: no more need for "receive_minimum".

@rainydio
Copy link

rainydio commented Jan 11, 2018

I'm sure just missing something. To "deposit" sender sends SEND+PoW, receiver replies with them same message signed with his private key. To "withdraw" receiver sends RECEIVE+PoW, sender replies with the same message signed with his private key.

@triwebb1
Copy link
Author

triwebb1 commented Jan 11, 2018

@rainydio - What you have described is not what the whitepaper describes. See page 3 section D.

@rainydio
Copy link

rainydio commented Jan 12, 2018

I know. Sorry, didn't had much time to explain. My question is why they are this way? PoW can be paid by transaction initiator.

Send

Here credit account is sending money (send transaction) to debit account.

send:
  # receiver of XRB
  debit: "xrb_3w...m37goeuufdp"
  # amount of XRB
  amount: "010a8044a0...1d49289d88c"
  # block in credit account
  block: "1967EA355...F2F3E5BF801"
  # proof of work
  pow: "000000000000EAE5"
  # whole message signed by credit
  signature: "83B0...006433265C7B204"

After processing send transaction node deducts balance from credit. When debit is ready to settle, it sends send_fin message to network.

send_fin:
  # original transaction
  send_transaction:
    # receiver of XRB
    debit: "xrb_3w...m37goeuufdp"
    # amount of XRB
    amount: "010a8044a0...1d49289d88c"
    # block in credit account
    block: "1967EA355...F2F3E5BF801"
    # proof of work
    pow: "000000000000EAE5"
    # whole message signed by credit
    signature: "83B0...006433265C7B204"

  # block in debit account
  block: DC04354B1...AE8FA2661B2,
  # debit signature of the whole message
  signature: B204...006433265C7B20483B0
}

Because send_fin contains original send transaction, node can settle send_fin transaction, even if it missed original send. Also send_fin does not contain pow field. Original send transaction already paid for send_fin.

This solves deposit to exchange case. But withdraw from exchange is slightly more complicated.

Withdraw

Here debit is requesting withdraw from credit.

withdraw:
  # sender of XRB, (recipient of request)
  credit: "xrb_eii...m37goe21fdp"
  # amount of XRB
  amount: "010a8044a0...1d49289d88c"
  # block in debit account
  block: "1967EA355...F2F3E5BF801"
  # proof of work
  pow: "000000000000EAE5"
  # whole message signed by debit
  signature: "83B0...006433265C7B204"

Although withdraw contains block field, and it's added to debit chain, transaction itself isn't changing the balance. Later credit sends withdraw_send transaction, which is similar to send, and deducts funds from credit balance.

withdraw_send:
  withdraw_transaction:
    # sender of XRB, (recipient of request)
    credit: "xrb_eii...m37goe21fdp"
    # amount of XRB
    amount: "010a8044a0...1d49289d88c"
    # block in debit account
    block: "1967EA355...F2F3E5BF801"
    # proof of work
    pow: "000000000000EAE5"
    # whole message signed by debit
    signature: "83B0...006433265C7B204"

  # block in credit account
  block: DC04354B1...AE8FA2661B2,
  # credit signature
  signature: B204...006433265C7B20483B0

Transfer isn't completed yet. Similar to send debit should send withdraw_send_fin. And so original withdraw transaction contains enough PoW to power three transactions.

withdraw_send_fin:
  withdraw_send_transaction:
    withdraw_transaction:
      # sender of XRB, (recipient of request)
      credit: "xrb_eii...m37goe21fdp"
      # amount of XRB
      amount: "010a8044a0...1d49289d88c"
      # block in debit account
      block: "1967EA355...F2F3E5BF801"
      # proof of work
      pow: "000000000000EAE5"
      # whole message signed by debit
      signature: "83B0...006433265C7B204"

    # block in credit account
    block: DC04354B1...AE8FA2661B2,
    # credit signature of the whole message
    signature: B204...006433265C7B20483B0

  # block in debit account
  block: DC04354B1...AE8FA2661B2,
  # debit signature
  signature: B204...006433265C7B20483B0

@triwebb1
Copy link
Author

triwebb1 commented Jan 12, 2018

@rainydio - If I understand your message correctly, you are proposing a different way to structure send and receives? The method you are describing sounds much less desirable to me than the current implementation in RaiBlocks because your method requires that the recipient of funds be online to approve and sign every SEND tx heading to the recipient. Simply removing the PoW requirement on RECEIVE txs and doing the necessary complimentary work sounds like a better idea to me.

@rainydio
Copy link

rainydio commented Jan 12, 2018

Recipient of funds be online to approve and sign every SEND tx heading to the recipient.

No.

Simply removing the PoW requirement on RECEIVE txs and doing the necessary complimentary work sounds like a better idea to me.

And that complimentary work...

The RECEIVE is claiming a SEND that this node has not yet received from the network, so hold it until synced, and rebroadcast to other nodes if confirmed valid in the future.

Which is basically a DoS attack vector to take down the node. But if original transaction is re-transmitted node can execute it. And that's it. Again but with code

# Broadcaster by sender
t_send:
  debit: "xrb_3w...m37goeuufdp"        # receiver of XRB
  amount: "010a8044a0...1d49289d88c"   # amount of XRB
  block: "1967EA355...F2F3E5BF801"     # block in sender account
  pow: "000000000000EAE5"              # proof of work
  signature: "83B0...006433265C7B204"  # whole message signed by sender

# Broadcaster by receiver later
t_send_fin:
  t_send:                                # renamed from send_transaction
    debit: "xrb_3w...m37goeuufdp"        # receiver of XRB
    amount: "010a8044a0...1d49289d88c"   # amount of XRB
    block: "1967EA355...F2F3E5BF801"     # block in sender account
    pow: "000000000000EAE5"              # proof of work
    signature: "83B0...006433265C7B204"  # whole message signed by sender
  block: DC04354B1...AE8FA2661B2         # block in receiver account
  signature: B204...006433265C7B20483B0  # receiver signature
}
pending_send_fin = PendingSendFinSet()

def on_send(t_send):
  acc_credit = account_of(t_send.signature)
  valid = \
    acc_credit.verify_signature(t_send) and \
    acc_credit.current_block == t_send.block and \
    acc_credit.balance >= t_send.amount  and \
    acc_credit.get_pow_amount(t_send.pow) >= 2 # paying for future `send_fin`

  if not valid:
    return False

  acc_credit.decrease_balance(t_send.amount)
  acc_credit.add_block(t_send.signature)

  pending_send_fin.add(t_send)
  propagate(t_send)

  return True

def on_send_fin(t_send_fin):
  if not pending_send_fin.contains(t_send_fin.t_send):
    if not on_send(t_send_fin.t_send):
      return False

  acc_debit = account_of(t_send_fin.signature)
  valid = \
    acc_debit.verify_signature(t_send_fin) and \
    acc_debit.address == t_send_fin.t_send.debit
    acc_debit.current_block == t_send_fin.block

  if not valid:
    return False

  acc_debit.increase_balance(t_send_fin.t_send.amount)
  acc_debit.add_block(t_send_fin.signature)

  pending_send_fin.remove(t_send_fin.t_send)
  propagate(t_send_fin)

  return True

@triwebb1
Copy link
Author

triwebb1 commented Jan 12, 2018

Sorry I misunderstood what you were saying before about credit and debit accounts, you were using the terms in the opposite way from what I interpreted.

Including the previous SEND in the SEND_FIN does not remove the DoS attack vector because the recipient of this SEND_FIN may not have the previous block that the encapsulated SEND is spending. I have not examined the current RaiBlocks codebase closely enough to understand how this problem is currently being handled. It seems logical that a buffer already exists to hold these, and if so then a mechanism probably exists to ask for any additional blocks form the network that are required to verify the chain. If I'm right then this is already an existing attack vector that may already have DoS prevention built around it, in which case the complimentary work that is required before disabling RECEIVE PoW is minimal or nothing.

@rainydio
Copy link

rainydio commented Jan 12, 2018

Renaming them to xrb_sender and xrb_receiver.

About transaction reordering. Actually, it appears that reordering is there. But generally peers should send transactions in order. And sync being separate global consistency check.

@rainydio
Copy link

rainydio commented Jan 12, 2018

Another attempt, this time with comments. Does it make sense?

SEND               = 0x01
SEND_FIN           = 0x02
WITHDRAW           = 0x03
WITHDRAW_SEND      = 0x04
WITHDRAW_SEND_FIN  = 0x05

OK                 = 0x00
ALREADY            = 0x01
BAD_SIGNATURE      = 0x02
BAD_PARENT         = 0x03
BAD_BALANCE        = 0x04
BAD_POW            = 0x04
BAD_STATE          = 0x06

BAD_SEND           = 0x10
BAD_WITHDRAW       = 0x11
BAD_WITHDRAW_SEND  = 0x12

# Transactions require PoW measured in median hash count.
# Numbers are arbitrary.
# Actually this needs another governance procedure

# two blocks and one unsettled transaction
SEND_PRICE = 2300

# three blocks and one unsettled transaction
WITHDRAW_PRICE = 4400

# set of `*_send` pending `*_fin`
unsettled = HashSet()

class Account
  def __constructor__(self):
    self.counter = 0
    self.balance = 0

    self.block = None

  def increase_balance(self, amount):
    self.balance += amount

  def decrease_balance(self, amount):
    self.balance -= amount
    assert(self.balance > 0)

  def get_pow_amount(self, pow):
    return get_median_hashes(self.current_block, pow)

  def add_block(self, transaction, expected_state):
    self.block = transaction.hash()

    if hash(self.block, self.counter, self.balance) != expected_state:
      return BAD_STATE

    return propagate(transaction, expected_state)

def on_send(t_send):
  """
    Deducts funds from `xrb_sender`.
    Mark transaction as unsettled.

    t_send {
      type = SEND

      byte[32] xrb_sender   # sender address
      byte[32] xrb_receiver # receiver address
      bigint   amount       # amount of XRB being sent
      byte[32] pow          # proof of work

      byte[32] parent       # parent block in xrb_sender account
      byte[64] signature    # xrb_sender signature
    }
  """

  xrb_sender = Account(t_send.xrb_sender)

  if xrb_sender.block == t_send.hash():
    return ALREADY
  if xrb_sender.verify_signature(t_send):
    return BAD_SIGNATURE
  if xrb_sender.block != t_send.parent:
    return BAD_PARENT
  if xrb_sender.balance < t_send.amount
    return BAD_BALANCE
  if xrb_sender.get_pow_amount(t_send.pow) < SEND_PRICE
    return BAD_POW

  xrb_sender.decrease_balance(t_send.amount)
  status = xrb_sender.add_block(t_send)
  if status == OK:
    unsettled.add(t_send) # store transaction hash until `t_send_fin`
  return status

def on_send_fin(t_send_fin):
  """
    Increase `xrb_receiver` by `amount`.
    Settle pending `t_send`.

    t_send_fin {
      type = SEND_FIN

      t_send {
        type = SEND

        byte[32] xrb_sender   # sender address
        byte[32] xrb_receiver # receiver address
        bigint   amount       # amount of XRB being sent
        byte[32] pow          # proof of work

        byte[32] parent       # parent block in xrb_sender account
        byte[64] signature    # xrb_sender signature
      }

      byte[32] parent         # parent block in xrb_receiver account
      byte[64] signature      # xrb_receiver signature
    }
  """

  t_send = t_send_fin.t_send
  xrb_receiver = Account(t_send.xrb_receiver)

  if xrb_receiver.block == t_send_fin.block:
    return ALREADY
  if not xrb_receiver.verify_signature(t_send_fin):
    return BAD_SIGNATURE
  if xrb_receiver.block != t_send_fin.parent;
    return BAD_PARENT

  if not unsettled.contains(t_send):
    # Three scenarios:
    #
    # Receiver got this message from another peer and quickly
    # replied with `send_fin`. This is preferred way, it increases
    # the chance of catching double spend early
    #
    # If `t_send_fin.t_send` can't be excuted
    #  * Node is overloaded and laks memory to store transaction hashes
    #    This is super unlikely and requires pre-mining
    #  * Original transaction was send long ago, this requires cryptographic
    #    proof that `send_fin.t_send` indeed took place. And additional lookup
    #    into journal to check for attempted double receive
    #  * Sender is executing double spend attack and this node previously got
    #    another 'send' transaction
    #
    #  It would be reasonable to request cryptographic proofs and PoW to
    #  compensate for disk lookup into history
    if on_send(t_send) != OK:
      # Request cryptographic proofs that t_send happened and additional PoW
      # to be committed (how?) to compensate for disk lookup
      return BAD_SEND

  xrb_receiver.increase_balance(t_send.amount)

  status = xrb_receiver.add_block(t_send_fin)
  if status == OK:
    unsettled.remove(t_send)
  return status

def on_withdraw(t_withdraw):
  """
    Request `withdraw_send` transaction from `xrb_sender`.
    Marked as unsettled.

    t_withdraw {
      type = WITHDRAW

      byte[32] xrb_sender   # sender address
      byte[32] xrb_receiver # receiver address
      bigint   amount       # requested amount of XRB
      byte[32] pow          # proof of work

      byte[32] parent       # parent block in xrb_receiver account
      byte[64] signature    # xrb_receiver signature
    }
  """

  xrb_receiver = Account(t_withdraw.xrb_receiver)

  if xrb_receiver.block == t_withdraw.block:
    return ALREADY
  if not xrb_receiver.verify_signature(t_withdraw):
    return BAD_SIGNATURE
  if xrb_receiver.block != t_withdraw.parent:
    return BAD_PARENT
  if xrb_receiver.get_pow_amount(t_withdraw.pow) < WITHDRAW_PRICE
    return BAD_POW

  status = xrb_receiver.add_block(t_send_fin)
  if status == OK:
    unsettled.add(t_withdraw)
  return status

def on_withdraw_send(t_withdraw_send):
  """
    Deducts funds from `xrb_sender`.
    Settle pending `t_withdraw`.
    Mark transaction as unsettled.

    t_withdraw_send {
      type = WITHDRAW_SEND

      t_withdraw {
        type = WITHDRAW

        byte[32] xrb_sender   # sender address
        byte[32] xrb_receiver # receiver address
        bigint   amount       # requested amount of XRB
        byte[32] pow          # proof of work

        byte[32] parent       # parent block in xrb_receiver account
        byte[64] signature    # xrb_receiver signature
      }

      byte[32] parent         # parent block in xrb_sender account
      byte[64] signature      # xrb_sender signature
    }
  """

  t_withdraw = t_withdraw_send.t_withdraw
  xrb_sender = Account(t_withdraw.xrb_sender)

  if xrb_sender.block == t_withdraw_send.block:
    return ALREADY
  if not xrb_sender.verify_signature(t_withdraw_send):
    return BAD_SIGNATURE
  if xrb_sender.block != t_withdraw_send.parent:
    return BAD_PARENT
  if xrb_sender.balance < t_withdraw.amount:
    return BAD_BALANCE

  if not unsettled.contains(t_withdraw):
    if on_withdraw(t_withdraw) != OK:
      return BAD_WITHDRAW

  xrb_sender.decrease_balance(t_withdraw.amount)

  status = xrb_sender.add_block(t_withdraw_send)
  if status == OK:
    unsettled.remove(t_withdraw)
    unsettled.add(t_withdraw_send)
  return status

def on_withdraw_send_fin(t_withdraw_send_fin):
  """
    Increase `xrb_receiver` by `amount`.
    Settle pending `t_withdraw_send`.

    t_withdraw_send_fin {
      type = WITHDRAW_SEND_FIN

      t_withdraw_send {
        type = WITHDRAW_SEND

        t_withdraw {
          type = WITHDRAW

          byte[32] xrb_sender   # sender address
          byte[32] xrb_receiver # receiver address
          bigint   amount       # requested amount of XRB
          byte[32] pow          # proof of work

          byte[32] parent       # parent block in xrb_receiver account
          byte[64] signature    # xrb_receiver signature
        }

        byte[32] parent         # parent block in xrb_sender account
        byte[64] signature      # xrb_sender signature
      }

      byte[32] parent           # parent block in xrb_receiver account
      byte[64] signature        # xrb_receiver signature
    }
  """

  t_withdraw_send = t_withdraw_send_fin.t_withdraw_send
  t_withdraw = t_withdraw_send.t_withdraw
  xrb_receiver = Account(t_withdraw.xrb_receiver)

  if xrb_receiver.block == t_withdraw_send_fin.block:
    return ALREADY
  if not xrb_receiver.verify_signature(t_withdraw_send_fin):
    return BAD_SIGNATURE
  if xrb_receiver.block != t_withdraw_send_fin.parent:
    return BAD_PARENT

  if not unsettled.contains(t_withdraw_send):
    if on_withdraw_send(t_withdraw_send) != OK:
      return BAD_WITHDRAW_SEND

  xrb_receiver.increase_balance(t_withdraw.amount)

  status = xrb_receiver.add_block(t_withdraw_send_fin)
  if status == OK:
    unsettled.remove(t_withdraw_send)
  return status

@Rorb
Copy link

Rorb commented Jan 15, 2018

https://www.reddit.com/r/RaiBlocks/comments/7qne70/raiblocks_receive_pow_necessary/

TL;DR: Receive-based PoW is necessary to keep pre-computed receive-fork attacks O(2^n) instead of O(log2(n!)) (~O(nlogn)).

I recommend this issue request be closed as a result.

@PlasmaPower
Copy link
Contributor

PlasmaPower commented Jan 15, 2018

@Rorb that was already mentioned here. I think eliminating PoW for receive blocks (in some form) is still a possibility.

@triwebb1
Copy link
Author

triwebb1 commented Jan 15, 2018

I have not yet read anything which suggests that blockchain length has anything to do with fork resolution. Why is a 1000 block fork any worse than a 2 block fork?

PoW on send prevents spam, but PoW on receive does not. I believe the only arguments I've read against removing PoW on receive are:

  1. Another DoS prevention mechanism will be required to stop bad actors from spamming invalid receive txs. Rate-limiting + bloom filter solution is proposed in this issue Remove PoW requirement on RECEIVE tx #464.

  2. Malicious receive forks may be more effective. I do not understand why this argument is valid though.

@Rorb
Copy link

Rorb commented Jan 16, 2018

@PlasmaPower I read up through the previous posts twice, and I am not seeing it discussed anywhere. Can you quote where valid-receive-order-forking was discussed? I see no mention of how the removal of PoW from Recv transactions would reduce attacker-work burden from O(2^n) to O(log(n!)), or any method of preventing that.

@triwebb1 A 1000 block fork is more dangerous than a 2-block fork because nodes can only resolve 1 one fork level at a time. If I fork (A->B+C) and then (B->E+F & C->G+H), the network cannot determine whether B, C, G, or H are valid UNTIL it FIRST determines whether B or C is valid. If I simply tried to fork (A->B+C+D+E+F+G+H), the network can simply say "A->B is the true fork" and outright discard the rest out-of-hand, triggering no secondary vote.

A 'fork depth' of 2 would trigger 2 votes. To create a 'fork depth' of n, I would need to make 2^n valid blocks, which would cost 2^n work. 2^n scales much much faster than n, which compensates for the fact that a network vote is much costlier than a single PoW. Since fork-depth is the real problem with the attack, the removal of PoW on receives would allow for extremely deep forks with minimal effort. An attacker would be able to trigger 'n' votes with a bit faster than nlog(n) PoW, which is substantially less work than 2^n. For 100 votes, it would be roughly 500-600 PoW's (at a rate of 6/s, that would be under 100 seconds). With PoW on receives, the attacker would need to create 2^100 PoW's before they could launch an attack with fork-depth of 100. 2^100 PoW's is around 10^33 or so, which is a hugely bigger number than "roughly 500-600."

@PlasmaPower
Copy link
Contributor

PlasmaPower commented Jan 16, 2018

@Rorb #464 (comment)

@triwebb1
Copy link
Author

triwebb1 commented Jan 16, 2018

@Rorb - Ah, so your concern isn't really that double-spends would be easier, it's that this opens a DoS attack vector by allowing a huge number of votes to be forced? I see. If the attacker's target knew that all this voting was going on to resolve the fork and therefore consider the balance for the attacker's account to be unsettled then this attack would never result in a successful double-spend. It is important to protect the network from voting-induced DoS though.

@rainydio
Copy link

rainydio commented Jan 16, 2018

Close it

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

7 participants